Submission #1045159

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1045159	2024-08-05T17:47:58 Z	ihceker	Strange Device (APIO19_strange_device)	C++14	35 / 100	890 ms	45456 KB

strange_device

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int32_t main(){
	int n,a,b;
	cin>>n>>a>>b;
	int x=a*b/__gcd(a,b+1);
	vector<pair<int,int>>pre;
	for(int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		if(r-l+1>=x){
			cout<<x<<endl;
			return 0;
		}
		if(l%x>r%x){
			pre.pb({0,1});
			pre.pb({r%x+1,-1});
			pre.pb({l%x,1});
			pre.pb({x,-1});
		}
		else{
			pre.pb({l%x,1});
			pre.pb({r%x+1,-1});
		}
	}
	sort(all(pre));
	int sum=0,ans=0,last=pre[0].ff;
	for(auto i:pre){
		if(sum>0){
			ans+=i.ff-last;
		}
		sum+=i.ss;
		last=i.ff;
	}
	cout<<ans<<endl;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	10 ms	1240 KB	Output is correct
3	Correct	13 ms	1240 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	444 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	9 ms	1384 KB	Output is correct
17	Correct	83 ms	7944 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	440 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	0 ms	348 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	456 KB	Output is correct
5	Correct	535 ms	38836 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	786 ms	44040 KB	Output is correct
3	Correct	780 ms	43164 KB	Output is correct
4	Correct	783 ms	44296 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	786 ms	44040 KB	Output is correct
3	Correct	780 ms	43164 KB	Output is correct
4	Correct	783 ms	44296 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	802 ms	44912 KB	Output is correct
7	Correct	801 ms	43660 KB	Output is correct
8	Correct	779 ms	43932 KB	Output is correct
9	Correct	839 ms	42692 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	786 ms	44040 KB	Output is correct
3	Correct	780 ms	43164 KB	Output is correct
4	Correct	783 ms	44296 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	81 ms	7352 KB	Output is correct
7	Correct	76 ms	8132 KB	Output is correct
8	Correct	74 ms	7360 KB	Output is correct
9	Correct	101 ms	7276 KB	Output is correct
10	Correct	84 ms	7396 KB	Output is correct
11	Correct	78 ms	6544 KB	Output is correct
12	Correct	75 ms	7616 KB	Output is correct
13	Correct	78 ms	8132 KB	Output is correct
14	Correct	77 ms	6248 KB	Output is correct
15	Correct	80 ms	7168 KB	Output is correct
16	Correct	95 ms	6348 KB	Output is correct
17	Correct	90 ms	7224 KB	Output is correct
18	Correct	812 ms	44964 KB	Output is correct
19	Correct	805 ms	43852 KB	Output is correct
20	Correct	802 ms	45456 KB	Output is correct
21	Correct	80 ms	7252 KB	Output is correct
22	Correct	76 ms	7620 KB	Output is correct
23	Correct	256 ms	21692 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	82 ms	6432 KB	Output is correct
3	Correct	78 ms	7100 KB	Output is correct
4	Correct	890 ms	44388 KB	Output is correct
5	Correct	85 ms	6844 KB	Output is correct
6	Correct	84 ms	7616 KB	Output is correct
7	Correct	88 ms	7340 KB	Output is correct
8	Correct	81 ms	6588 KB	Output is correct
9	Correct	97 ms	7392 KB	Output is correct
10	Correct	109 ms	6336 KB	Output is correct
11	Correct	84 ms	8028 KB	Output is correct
12	Correct	76 ms	7412 KB	Output is correct
13	Correct	81 ms	7516 KB	Output is correct
14	Correct	802 ms	34132 KB	Output is correct
15	Correct	81 ms	5316 KB	Output is correct
16	Correct	740 ms	34340 KB	Output is correct
17	Correct	769 ms	34728 KB	Output is correct
18	Incorrect	0 ms	344 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	10 ms	1240 KB	Output is correct
3	Correct	13 ms	1240 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	444 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	9 ms	1384 KB	Output is correct
17	Correct	83 ms	7944 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1045159

Compilation message