Submission #1045157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1045157	2024-08-05T17:47:13 Z	vjudge1	Strange Device (APIO19_strange_device)	C++17	35 / 100	1010 ms	54392 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	1 ms	604 KB	Output is correct
2	Correct	14 ms	1420 KB	Output is correct
3	Correct	15 ms	1452 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 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	11 ms	1260 KB	Output is correct
17	Correct	88 ms	8640 KB	Output is correct
18	Incorrect	0 ms	344 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	440 KB	Output is correct
3	Correct	1 ms	436 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	2 ms	604 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	567 ms	46840 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	920 ms	52552 KB	Output is correct
3	Correct	959 ms	51940 KB	Output is correct
4	Correct	850 ms	52308 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	920 ms	52552 KB	Output is correct
3	Correct	959 ms	51940 KB	Output is correct
4	Correct	850 ms	52308 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	902 ms	53344 KB	Output is correct
7	Correct	874 ms	52516 KB	Output is correct
8	Correct	853 ms	53192 KB	Output is correct
9	Correct	876 ms	53284 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	920 ms	52552 KB	Output is correct
3	Correct	959 ms	51940 KB	Output is correct
4	Correct	850 ms	52308 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	79 ms	7848 KB	Output is correct
7	Correct	99 ms	7704 KB	Output is correct
8	Correct	92 ms	7848 KB	Output is correct
9	Correct	85 ms	5960 KB	Output is correct
10	Correct	82 ms	7108 KB	Output is correct
11	Correct	83 ms	8056 KB	Output is correct
12	Correct	81 ms	7464 KB	Output is correct
13	Correct	85 ms	7112 KB	Output is correct
14	Correct	83 ms	7108 KB	Output is correct
15	Correct	111 ms	6712 KB	Output is correct
16	Correct	86 ms	7868 KB	Output is correct
17	Correct	93 ms	7584 KB	Output is correct
18	Correct	860 ms	52224 KB	Output is correct
19	Correct	792 ms	51896 KB	Output is correct
20	Correct	841 ms	53556 KB	Output is correct
21	Correct	84 ms	6600 KB	Output is correct
22	Correct	83 ms	6332 KB	Output is correct
23	Correct	268 ms	23696 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	84 ms	8116 KB	Output is correct
3	Correct	111 ms	7872 KB	Output is correct
4	Correct	868 ms	53288 KB	Output is correct
5	Correct	84 ms	7108 KB	Output is correct
6	Correct	88 ms	7392 KB	Output is correct
7	Correct	101 ms	8128 KB	Output is correct
8	Correct	86 ms	6336 KB	Output is correct
9	Correct	102 ms	7788 KB	Output is correct
10	Correct	85 ms	6852 KB	Output is correct
11	Correct	89 ms	7868 KB	Output is correct
12	Correct	83 ms	6796 KB	Output is correct
13	Correct	87 ms	6588 KB	Output is correct
14	Correct	1010 ms	54392 KB	Output is correct
15	Correct	87 ms	6588 KB	Output is correct
16	Correct	834 ms	52964 KB	Output is correct
17	Correct	818 ms	53640 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	1 ms	604 KB	Output is correct
2	Correct	14 ms	1420 KB	Output is correct
3	Correct	15 ms	1452 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 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	11 ms	1260 KB	Output is correct
17	Correct	88 ms	8640 KB	Output is correct
18	Incorrect	0 ms	344 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1045157

Compilation message