QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215977 | #1780. Intact Intervals | PhantomThreshold# | WA | 10ms | 24108kb | C++20 | 1.8kb | 2023-10-15 14:52:25 | 2023-10-15 14:52:25 |
Judging History
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;
}
詳細信息
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'