QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215977#1780. Intact IntervalsPhantomThreshold#WA 10ms24108kbC++201.8kb2023-10-15 14:52:252023-10-15 14:52:25

Judging History

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

  • [2023-10-15 14:52:25]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:24108kb
  • [2023-10-15 14:52:25]
  • 提交

answer

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

const int maxn = 1050000;
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;
		f[j]=(f[j]+cc)%mod;
	}
	int ans=0;
	for(int i=1;i<=cnt;i++) (ans+=f[i])%=mod;
	ans=(ans+mod-n-2)%mod;
	cout<<ans<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 24108kb

input:

2
10 9
9 10

output:

0

result:

ok single line: '0'

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 21200kb

input:

5
3 6 9 10 6
3 10 6 9 6

output:

10

result:

wrong answer 1st lines differ - expected: '4', found: '10'