QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#42292#1780. Intact IntervalspskkkWA 7ms16772kbC++171.9kb2022-08-01 20:59:292022-08-01 20:59:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-01 20:59:32]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:16772kb
  • [2022-08-01 20:59:29]
  • 提交

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(x&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]+val[a[i]]-val[b[i]];
		psum2[i]=psum2[i-1]+qpow(19260817,val2[a[i]])-qpow(19260817,val2[a[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: 16072kb

input:

2
10 9
9 10

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 2ms
memory: 16040kb

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: 2ms
memory: 15920kb

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: 2ms
memory: 16044kb

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: 2ms
memory: 16044kb

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: 2ms
memory: 16084kb

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: 7ms
memory: 16736kb

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: 5ms
memory: 16772kb

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: 3ms
memory: 16276kb

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:

366102962

result:

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