QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216005#1780. Intact IntervalsPhantomThreshold#Compile Error//C++201.9kb2023-10-15 15:06:212023-10-15 15:06:21

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 15:06:21]
  • 评测
  • [2023-10-15 15:06:21]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 2050000;
const int mod  = 1e9+7;
const int mod1 = 998244353;
const int mod2 = 1e9+7;
const int b1   = 19260817;
const int b2   = 104857601;

struct Hash
{
	int x,y;
	friend inline Hash operator +(const Hash &k1,const Hash &k2) { return (Hash){(k1.x+k2.x)%mod1,(k1.y+k2.y)%mod2}; }
	friend inline Hash operator -(const Hash &k1,const Hash &k2) { return (Hash){(k1.x-k2.x+mod1)%mod1,(k1.y-k2.y+mod2)%mod2}; }
	friend inline Hash operator *(const Hash &k1,const Hash &k2) { return (Hash){(ll)k1.x*k2.x%mod1,(ll)k1.y*k2.y%mod2}; }
	friend inline Hash operator *(const Hash &k1,const int &k2){ return (Hash){(ll)k1.x*k2%mod1,(ll)k1.y*k2%mod2}; }
}h[maxn],pw[maxn];

int n;
int a[maxn],b[maxn];
int t[maxn],tp;
map<int,int>mp;

int numa[maxn],numb[maxn];

map< pair<int,int>, int >mph; int cnt;
int id[maxn];
int f[maxn];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],t[++tp]=a[i];
	for(int i=1;i<=n;i++) cin>>b[i],t[++tp]=b[i];
	
	sort(t+1,t+tp+1);
	tp=unique(t+1,t+tp+1)-t-1;
	for(int i=1;i<=tp;i++) mp[t[i]]=i;
	
	for(int i=1;i<=n;i++) a[i]=mp[a[i]];
	for(int i=1;i<=n;i++) b[i]=mp[b[i]];
	
	pw[0]=(Hash){1,1};
	pw[1]=(Hash){b1,b2};
	for(int i=2;i<maxn;i++) pw[i]=pw[i-1]*pw[1];
	
	h[0]=(Hash){0,0};
	for(int i=1;i<=tp;i++) h[0]=h[0] + (pw[i]*1000000);
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1];
		h[i]= h[i]+pw[a[i]]-pw[b[i]];
	}
	
	for(int i=0;i<=n;i++)
	{
		pair<int,int>temp(h[i].x,h[i].y);
		if(mph.count(temp)==0) mph[temp]=++cnt;
		id[i]=mph[temp];
	}
	
	for(int i=0;i<n;i++)
	{
		int j=id[i];
		
		int cc= f[j]+1;
		//cerr<<i<<" : "<<cc<<endl;
		f[j]=(f[j]+cc)%mod;
	}
	int ans=0;
	for(int i=1;i<=cnt;i++) (ans+=f[i])%=mod;
	ans=(ans+mod-n)%mod;
	cout<<ans<<endl;
	
	return 0;
}

Details

cc1plus: error: ‘::main’ must return ‘int’