QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#42299 | #1780. Intact Intervals | pskkk | WA | 3ms | 16060kb | C++17 | 1.8kb | 2022-08-01 21:09:44 | 2022-08-01 21:09:46 |
Judging History
answer
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define File(a) freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
using namespace std;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
}
int pw[1000005];
const int mod=1e9+7;
mt19937_64 rng(2333333),rng2(19260817);
vector<int>g;
int n;
int a[1000005], b[1000005];
unsigned long long val[1000005],val2[1000005];
unsigned long long psum[1000005],psum2[1000005];
unsigned long long qpow(unsigned long long x,unsigned long long y){
unsigned long long res=1;
while(y){
if(y&1)res=res*x;
x=x*x;
y>>=1;
}
return res;
}
void solve(){
n=read();
pw[0]=1;
F(i,1,n)a[i]=read(),g.push_back(a[i]),pw[i]=2ll*pw[i-1]%mod;
F(i,1,n)b[i]=read();
sort(g.begin(),g.end());
g.resize(unique(g.begin(),g.end())-g.begin());
F(i,1,n)a[i]=lower_bound(g.begin(),g.end(),a[i])-g.begin(),b[i]=lower_bound(g.begin(),g.end(),b[i])-g.begin();
F(i,0,g.size()-1)val[i]=rng(),val2[i]=rng2();
map<unsigned long long, int>cnt;
int res=0;
F(i,1,2*n){
psum[i]=psum[i-1]+qpow(998244353,a[i])-qpow(998244353,b[i]);
if(i>n){
cnt[psum[i-n]]--;
res=(res+pw[cnt[psum[i]]]-1+mod)%mod;
}
if(i<=n)cnt[psum[i]]++;
}
printf("%d\n",res);
}
int main () {
#ifndef ONLINE_JUDGE
File();
#endif
int T=1;
// cin>>T;
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 16060kb
input:
2 10 9 9 10
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'