QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #277601 | #1780. Intact Intervals | wangqingxian | WA | 4ms | 5520kb | C++14 | 1.6kb | 2023-12-06 20:40:25 | 2023-12-06 20:40:26 |
Judging History
answer
#include<algorithm>
#include<vector>
#include<cstdio>
#include<map>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<bitset>
#include<queue>
#include<cassert>
#include<stdlib.h>
#include<cmath>
#include<set>
#define ll long long
#define ld long double
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define rof(i,r,l) for(int i=(r);i>=(l);--i)
#define db double
#define mem0(a) memset(a,0,sizeof(a))
#define ull unsigned long long
#define lowbit(t) (t&-t)
#define uint unsigned int
//#define int long long
#define pii pair<int,int>
#define x1 dlskjfakljflkasd
#define y1 sldkfjalfjkalskl
#define x2 sdalkfjaklfjsdlk
#define y2 sfjaofoiwjfwfwof
using namespace std;
const int N=1e6+10,inf=2147483647,mod=998244353;
const ull base=1145141;
int n;
int a[N],b[N];
ull h1[N],h2[N];
ull fang[N];
int c[N],m;
int ans=0;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
For(i,1,n){cin>>a[i];c[++m]=a[i];}
For(i,1,n){cin>>b[i];c[++m]=b[i];}
sort(c+1,c+1+m);
m=unique(c+1,c+1+m)-c-1;
fang[0]=1;
For(i,1,m)fang[i]=fang[i-1]*base;
For(i,1,n){
h1[i]=h1[i-1]+fang[lower_bound(c+1,c+1+m,a[i])-c];
h2[i]=h2[i-1]+fang[lower_bound(c+1,c+1+m,b[i])-c];
}
For(i,1,n)h1[i]-=h2[i];
sort(h1+1,h1+1+n);
int cnt=0;
For(i,1,n){
cnt++;
if(h1[i]!=h1[i+1]||i==n){
ans=(ans+(1<<cnt)%mod-1)%mod;
cnt=0;
}
}
cout<<(ans-n+mod)%mod<<endl;
return 0;
}
/*
5
1 2 2 3 4
4 3 2 2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5520kb
input:
2 10 9 9 10
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3360kb
input:
5 3 6 9 10 6 3 10 6 9 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
10 10 10 0 4 0 5 3 8 5 3 3 0 8 5 0 4 3 10 5 10
output:
9
result:
ok single line: '9'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
100 53 74 39 7 86 14 54 63 86 33 1 33 94 28 65 93 79 52 3 22 53 20 69 59 29 8 42 7 18 33 27 72 10 19 65 30 29 1 57 39 41 6 9 5 92 15 99 22 72 18 81 7 51 82 57 28 4 27 65 99 55 8 57 76 61 13 19 89 9 79 76 95 11 68 9 52 79 24 99 52 65 30 34 77 64 99 10 30 41 12 91 90 13 24 76 41 26 84 51 22 99 89 24 5...
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
100 1 8 7 6 4 6 8 10 9 10 7 8 8 9 7 5 7 8 7 10 10 0 2 5 6 6 5 4 1 8 3 1 8 0 3 2 0 8 0 8 6 0 1 2 2 2 0 10 5 0 6 4 2 8 8 10 5 1 1 5 8 9 9 0 6 7 3 0 3 6 5 8 4 9 2 9 2 8 3 4 5 0 3 10 6 9 7 0 10 9 9 8 5 10 0 1 8 2 2 10 4 0 3 8 2 6 5 6 10 4 10 8 3 8 4 8 6 0 1 0 2 7 0 5 1 6 9 0 7 2 0 1 5 5 7 6 0 9 10 4 0 2...
output:
13
result:
ok single line: '13'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
100 1 2 0 0 2 1 1 1 1 1 0 0 2 0 1 2 1 0 0 2 1 2 0 2 0 0 1 2 2 2 0 0 0 1 1 1 1 0 0 0 2 2 2 2 0 2 1 2 2 1 2 1 1 1 1 2 2 0 1 0 0 0 0 1 0 1 2 0 2 2 2 1 1 2 1 1 0 1 2 2 0 2 2 1 2 1 1 1 1 2 0 1 1 2 0 1 0 2 2 0 0 1 1 1 1 2 2 1 0 0 2 2 0 0 1 0 2 2 1 0 1 2 2 0 1 1 1 2 1 0 0 2 2 0 1 1 1 0 1 1 2 1 2 2 2 1 2 2 ...
output:
1075
result:
ok single line: '1075'
Test #7:
score: 0
Accepted
time: 4ms
memory: 3836kb
input:
10000 2140 5310 9949 84 2706 4404 6310 8451 6995 8883 4817 8214 1668 4724 1674 839 2900 7773 8536 3712 3056 4683 405 1826 9937 5284 9614 8701 4235 8394 4678 6904 3425 2458 2343 6893 5819 5207 370 9231 3018 2552 1381 4495 8465 2312 6937 907 3333 4236 8006 6939 4945 1667 1528 5043 5298 2278 3634 6824 ...
output:
4
result:
ok single line: '4'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
10000 82 19 42 67 24 91 33 53 56 16 30 88 22 26 13 99 93 98 62 6 18 34 75 91 91 39 16 56 68 67 36 90 86 39 10 20 37 52 56 4 69 18 97 82 48 35 21 7 24 42 95 99 66 47 1 37 42 90 86 47 36 82 67 27 11 58 62 10 29 10 87 12 73 62 64 27 58 39 36 98 43 25 76 37 96 39 65 64 61 45 65 80 23 56 95 49 45 69 70 5...
output:
117
result:
ok single line: '117'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 3776kb
input:
10000 0 1 0 1 2 2 2 2 2 0 1 0 0 1 1 2 0 2 1 0 1 2 2 1 1 1 2 0 2 2 0 0 2 2 1 0 2 1 2 2 2 0 2 1 2 1 2 0 2 2 0 1 0 1 0 1 0 0 0 1 1 0 1 2 0 1 0 2 0 1 2 0 1 2 1 0 1 2 2 0 2 1 1 1 0 2 1 0 2 1 2 0 2 0 0 0 1 0 1 1 2 2 2 0 0 1 2 2 0 1 1 0 2 1 2 1 1 0 2 1 2 0 0 2 1 1 2 1 0 2 1 0 2 2 1 2 1 0 0 0 1 2 1 2 0 2 2 ...
output:
72891350
result:
wrong answer 1st lines differ - expected: '661070230', found: '72891350'