QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#42302 | #1780. Intact Intervals | pskkk | WA | 4ms | 16068kb | C++17 | 1.9kb | 2022-08-01 21:11:22 | 2022-08-01 21:11:26 |
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[2000005];
const int mod=1e9+7;
mt19937_64 rng(2333333),rng2(19260817);
vector<int>g;
int n;
int a[2000005], b[2000005];
unsigned long long val[2000005],val2[2000005];
unsigned long long psum[2000005],psum2[2000005];
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,a[i+n]=a[i];
F(i,1,n)b[i]=read(),b[i+n]=b[i];
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 15952kb
input:
2 10 9 9 10
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 3ms
memory: 16068kb
input:
5 3 6 9 10 6 3 10 6 9 6
output:
4
result:
ok single line: '4'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 15956kb
input:
10 10 10 0 4 0 5 3 8 5 3 3 0 8 5 0 4 3 10 5 10
output:
0
result:
wrong answer 1st lines differ - expected: '9', found: '0'