后四个点TLE,应该不会超时?
查看原帖
后四个点TLE,应该不会超时?
50787
zzzty___楼主2021/3/4 23:45
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn];
long long ans=0;
int trie[maxn*5][100],en[maxn*5],cnt=1;	
inline int id(char ch){return ch-'A'; }
void insert(char* str,int rk)
{
	int len=strlen(str),p=1;
	for(int i=0;i<len;i++)
	{
		int ch=id(str[i]);
		if(!trie[p][ch])trie[p][ch]=++cnt;
		p=trie[p][ch];
	}
	en[p]=rk;
} 
int search(char* str)
{
	int len=strlen(str),p=1;
	for(int i=0;i<len;i++)
		p=trie[p][id(str[i])];
	return en[p];
}
void merge_sort(int l,int r)
{
	if(l>=r) return;
	int mid=l+r>>1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int i=l,j=mid+1,k=l,t[maxn];
	memset(t,0,sizeof(t));
	while(i<=mid&&j<=r)
	{
		if(a[i]>a[j])
		{
			t[k++]=a[j++];
			ans+=mid-i+1;
		}
		else t[k++]=a[i++];
	}
	while(i<=mid)t[k++]=a[i++];
	while(j<=r)t[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=t[i];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		char str[6];
		scanf("%s",&str);
		insert(str,i);
	}
	for(int i=1;i<=n;i++)
	{
		char str[6];
		scanf("%s",&str);
		a[i]=search(str);
	}
	merge_sort(1,n);
	cout<<ans<<endl;
	return 0;
}
2021/3/4 23:45
加载中...