后四个点MLE求助
查看原帖
后四个点MLE求助
313137
qqqqq111楼主2021/10/25 18:45

别人都是wa怎么就我mle

rt。qwq

#include<iostream>
#include<string>

#define N 100005
#define copy cpy

using namespace std;

int n;
int trie[N*3][126];
int count[N*3];
int cnt;
int tot;
int arr[N*3];
int copy[N*3];
int ans;

inline void insrt(string s) {
	int len=s.size(), p=1;
	for(int i=0; i<len; i++) {
		int ch=s[i]-'0';
		if(trie[p][ch]==0)
			trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	count[p]=++cnt;
}
inline int fnd(string s) {
	int len=s.size(), p=1; 
	for(int i=0; i<len; i++) {
		int ch=s[i]-'0';
		if(!trie[p][ch])
			break;
		p=trie[p][ch];
	}
	return count[p];
}
void msort(int l, int r) {
	if(l==r)
		return ;
	int mid((l+r)>>1);
	msort(l, mid);
	msort(mid+1, r);
	
	int i=l, j=mid+1, k=l;
	while(i<=mid && j<=r)
		if(arr[i]<arr[j])
			copy[k++]=arr[i++];
		else 
			copy[k++]=arr[j++], ans+=mid-i+1;
			
	while(i<=mid)
		copy[k++]=arr[i++];
	while(j<=r)
		copy[k++]=arr[j++];
		
	for(int i=l; i<=r; i++)
		arr[i]=copy[i];
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	for(int i=0; i<n; i++) {
		string s;
		cin>>s;
		insrt(s);
	}
	for(int i=0; i<n; i++) {
		string s;
		cin>>s;
		arr[i]=fnd(s);
	}
	msort(0, n-1);
	cout<<ans;
	return 0;
}
2021/10/25 18:45
加载中...