QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#42297 | #1780. Intact Intervals | pskkk | WA | 3508ms | 109948kb | C++17 | 1.9kb | 2022-08-01 21:05:26 | 2022-08-01 21:05:27 |
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<pair<unsigned long long,unsigned long long>, int>cnt;
F(i,1,n){
psum[i]=psum[i-1]+qpow(998244353,val[a[i]])-qpow(998244353,val[b[i]]);
psum2[i]=psum2[i-1]+qpow(19260817,val2[a[i]])-qpow(19260817,val2[b[i]]);
cnt[{psum[i],psum2[i]}]++;
}
int res=0;
for(auto &p : cnt){
res=(res+pw[p.second]-p.second-1+mod)%mod;
}
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: 100
Accepted
time: 3ms
memory: 15988kb
input:
2 10 9 9 10
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 3ms
memory: 15952kb
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: 4ms
memory: 15996kb
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: 3ms
memory: 16108kb
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: 3ms
memory: 16000kb
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: 16100kb
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: 9ms
memory: 16780kb
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: 9ms
memory: 16704kb
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: 0
Accepted
time: 0ms
memory: 16152kb
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:
661070230
result:
ok single line: '661070230'
Test #10:
score: 0
Accepted
time: 3508ms
memory: 108364kb
input:
1000000 53619079 982512764 860871815 530378910 588856185 454683791 264369639 297818635 824975749 256072724 56501959 644097074 258832116 294895621 430606412 64927560 98316617 241951788 814040050 543600636 502382486 898906645 914890506 424109890 191843578 913062126 513568981 753685691 579339567 739779...
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 3117ms
memory: 109948kb
input:
1000000 379491 423615 303730 616005 716043 660165 422058 952047 984874 839411 652625 702220 614558 70068 45650 997250 623100 492984 574610 956181 940400 495685 33538 602760 846707 464330 305563 545858 20911 407856 871126 568332 726681 420978 712188 759802 771108 187839 109384 781142 105828 750540 44...
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 2132ms
memory: 99600kb
input:
1000000 646696897 307550750 352055156 145493783 876454664 99776544 86852880 16750429 214290945 969506283 772309271 753769454 104954710 772309271 467856522 214125155 848614965 930244030 16750429 104954710 245368159 891572304 2439115 750700204 929485372 946025151 428706915 960038923 2439115 784399861 ...
output:
10274
result:
ok single line: '10274'
Test #13:
score: 0
Accepted
time: 2990ms
memory: 108496kb
input:
1000000 67606 412951 730949 182648 124844 759671 310913 632762 622832 812614 102462 66728 706288 593038 496173 902778 732591 99404 414562 361946 977273 513531 206369 484027 547467 881498 597662 330888 912299 900729 287461 113436 169944 166886 694667 655130 91758 393634 419028 830888 219038 945816 44...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 2316ms
memory: 100444kb
input:
1000000 8299 4940 3492 9449 9679 5280 656 1666 8852 89 9995 1167 1425 8702 2245 1819 8035 2246 9575 9363 3943 3488 937 9164 7637 2919 8724 839 8758 8049 5826 1149 2863 9972 7323 6431 6308 4642 3292 9613 5792 5585 3769 2974 5843 9553 8978 261 6327 8466 1666 8018 9543 7760 4012 8581 4310 4547 3795 802...
output:
92
result:
ok single line: '92'
Test #15:
score: 0
Accepted
time: 1991ms
memory: 99660kb
input:
1000000 95 91 68 69 69 98 20 3 84 13 64 82 98 35 44 82 26 30 83 76 61 100 81 22 45 28 96 14 39 33 40 15 3 63 86 3 29 33 99 0 14 57 30 54 85 4 1 82 42 69 66 45 1 25 91 30 47 88 61 96 27 2 46 96 13 22 5 29 50 45 47 93 64 31 19 47 42 97 27 92 10 37 82 88 84 27 57 13 78 54 88 44 18 99 64 78 60 46 38 36 ...
output:
10194
result:
ok single line: '10194'
Test #16:
score: 0
Accepted
time: 1534ms
memory: 94040kb
input:
1000000 3 8 3 6 10 2 5 2 7 8 0 1 5 1 8 9 0 2 2 6 8 9 6 3 6 6 6 8 5 2 10 1 2 10 10 1 0 8 2 9 1 2 2 4 1 0 8 4 7 8 5 5 5 7 5 3 6 4 1 0 7 9 10 2 1 6 8 10 3 4 3 5 10 3 5 9 9 0 0 1 1 6 7 2 2 3 0 7 8 4 0 0 4 8 0 1 1 5 7 6 0 0 6 7 10 8 6 1 8 2 3 6 1 7 1 1 4 7 3 1 5 6 1 9 2 7 1 3 7 6 0 10 8 5 6 1 0 9 1 8 6 9...
output:
126874
result:
ok single line: '126874'
Test #17:
score: 0
Accepted
time: 1124ms
memory: 88876kb
input:
1000000 1 4 3 0 2 4 5 5 2 2 3 5 5 2 1 2 3 3 4 5 0 2 5 1 1 2 3 0 0 5 1 2 4 1 3 5 4 5 0 1 0 3 3 4 1 5 4 5 3 5 0 0 0 2 1 5 1 3 0 0 2 1 2 5 1 5 3 2 3 5 2 3 2 2 1 3 3 1 3 5 2 4 1 3 1 1 1 2 0 3 5 0 5 1 4 4 1 0 1 4 2 2 1 3 3 5 0 0 0 3 2 0 3 3 2 4 2 3 1 0 5 3 4 2 5 2 3 5 3 2 0 0 5 2 5 3 1 0 0 4 1 4 3 4 4 1 ...
output:
379607
result:
ok single line: '379607'
Test #18:
score: -100
Wrong Answer
time: 421ms
memory: 47764kb
input:
1000000 2 1 1 0 1 2 2 0 0 0 1 2 2 2 0 2 2 1 1 2 0 1 2 1 2 1 1 0 0 1 0 2 2 0 1 1 1 1 0 0 0 0 2 2 0 0 1 1 2 2 1 2 0 1 0 1 0 2 0 1 0 1 2 0 2 2 0 2 2 1 1 2 2 0 2 0 1 0 0 1 2 2 2 1 1 2 1 1 2 0 2 0 1 2 2 0 1 2 0 2 0 0 2 0 0 0 0 1 2 1 1 0 0 2 2 0 2 0 0 2 1 0 1 2 0 0 0 1 1 2 0 0 0 2 2 1 2 0 2 0 0 0 1 1 2 1 ...
output:
298967235
result:
wrong answer 1st lines differ - expected: '681495559', found: '298967235'