QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#221939	#1780. Intact Intervals	zhouyixian	WA	1201ms	86236kb	C++14	939b	2023-10-21 15:06:25	2023-10-21 15:06:26

Judging History

你现在查看的是最新测评结果

[2023-10-21 15:06:26]
评测

测评结果：WA
用时：1201ms
内存：86236kb

查看

[2023-10-21 15:06:25]
提交

answer

#include<bits/stdc++.h>
#include<random>
using namespace std;
const int N=1e6+10,mod=1e9+7,MOD=1e11+7;
#define ull unsigned long long
int n,id[N],pow2[N];
int cnt[N],tot;
ull v[N],h[N],a[N],b[N];

mt19937 mt(time(0));

map<int,ull> hsh;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	pow2[0]=1;
	for(int i=1;i<=n;++i)
		pow2[i]=(pow2[i-1]<<1)%mod;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(!hsh.count(a[i]))
			hsh[a[i]]=mt()+1ll*(a[i]+113)*(a[i]+517)%MOD;
		a[i]=hsh[a[i]];
	}
	for(int i=1;i<=n;++i){
		cin>>b[i];
		b[i]=hsh[b[i]];
	}
	ull ha=0,hb=0;
	for(int i=1;i<=n;++i){
		ha+=a[i];
		hb+=b[i];
		h[i]=v[i]=ha-hb;
	}
	sort(v+1,v+n+1);
	tot=unique(v+1,v+n+1)-v;
	for(int i=1;i<=n;++i)
		id[i]=lower_bound(v+1,v+tot,h[i])-v;
	for(int i=1;i<=n;++i)
		cnt[id[i]]++;
	long long ans=0;
	for(int i=1;i<=tot;++i)
		ans+=pow2[cnt[i]]-cnt[i]-1;
	cout<<ans%mod<<endl;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 12024kb

input:

2
10 9
9 10

output:

result:

ok single line: '0'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3764kb

input:

5
3 6 9 10 6
3 10 6 9 6

output:

result:

ok single line: '4'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3768kb

input:

10
10 10 0 4 0 5 3 8 5 3
3 0 8 5 0 4 3 10 5 10

output:

result:

ok single line: '9'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3784kb

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:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3776kb

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:

result:

ok single line: '13'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3780kb

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:

result:

ok single line: '1075'

Test #7:

score: 0

Accepted

time: 5ms

memory: 4536kb

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:

result:

ok single line: '4'

Test #8:

score: 0

Accepted

time: 3ms

memory: 4208kb

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:

result:

ok single line: '117'

Test #9:

score: 0

Accepted

time: 2ms

memory: 4176kb

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: -100

Wrong Answer

time: 1201ms

memory: 86236kb

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:

result:

wrong answer 1st lines differ - expected: '1', found: '2'