Submission #545378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545378	2022-04-04T12:02:06 Z	amunduzbaev	Strange Device (APIO19_strange_device)	C++17	30 / 100	2168 ms	219428 KB

strange_device

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define i128 __int128
#define int long long

int bp(int a, int b, int mod){
	int r = 1;
	while(b){
		if(b&1){
			r = (i128)r * (i128)a % mod;
		} a = (i128)a * (i128)a % mod, b >>= 1;
	} return r;
}

/*

3 5 12
0 23
60 60
81 83

*/

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, A, B; cin>>n>>A>>B;
	vector<ar<int, 2>> s(n);
	for(int i=0;i<n;i++){
		cin>>s[i][0]>>s[i][1];
	}
	
	int D = B + 1;
	int G = __gcd(A, D);
	vector<ar<int, 3>> ss;
	vector<ar<int, 2>> a;
	for(int i=0;i<n;i++){
		int l = s[i][0], r = s[i][1];
		int bl = l / B, br = r / B;
		if(bl == br){
			ss.push_back({l % B, r % B, (bl*D) % A / G});
		} else {
			ss.push_back({l % B, B - 1, (bl*D) % A / G});
			ss.push_back({0, r % B, (br*D) % A / G});
			int c = (br - bl - 1);
			if(c){
				a.push_back({((bl+1)*D) % A / G, c});
			}
		}
	}
	
	A /= G, D /= G;
	int res = 0;
	//~ if(A == 1 && !a.empty()){
		//~ cout<<B<<"\n";
		//~ return 0;
	//~ }
	
	vector<ar<int, 2>> tot;
	i128 inv = 0;
	if(!a.empty()){
		if(A > 1) inv = bp(D, A - 2, A);
		for(auto& x : a){
			x[0] = (i128)x[0] * inv % A;
			if(x[1] >= A){
				cout<<A * B<<"\n";
				return 0;
			}
			x[1] = (x[0] + x[1] - 1) % A;
			if(x[0] <= x[1]) tot.push_back({x[0], x[1]});
			else {
				tot.push_back({x[0], A - 1});
				tot.push_back({0, x[1]});
			}
		}
		
		sort(tot.begin(), tot.end());
		int r = -1;
		for(auto& x : tot){
			if(r < x[0]){
				res += (x[1] - x[0] + 1) * B;
				r = x[1];
			} else if(r < x[1]){
				res += (x[1] - r) * B;
				r = x[1];
			} x[1] = r;
		}
	}
	
	sort(ss.begin(), ss.end());
	map<int, int> mm;
	for(auto& x : ss){
		if(!a.empty()){
			int p = (i128)x[2] * inv % A;
			auto it = lower_bound(tot.begin(), tot.end(), (ar<int, 2>){p + 1, -1});
			if(it != tot.begin()){
				it--;
				if(p <= (*it)[1]) continue;
			}
		}
		
		if(!mm.count(x[2]) || mm[x[2]] < x[0]) res += (x[1] - x[0] + 1), mm[x[2]] = x[1];
		else if(mm[x[2]] < x[1]) res += (x[1] - mm[x[2]]), mm[x[2]] = x[1];
	}
	
	cout<<res<<"\n";
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	7 ms	944 KB	Output is correct
3	Correct	6 ms	916 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Incorrect	1 ms	212 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #3
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	2 ms	468 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1065 ms	102068 KB	Output is correct
3	Correct	2168 ms	219404 KB	Output is correct
4	Correct	2131 ms	219428 KB	Output is correct

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1065 ms	102068 KB	Output is correct
3	Correct	2168 ms	219404 KB	Output is correct
4	Correct	2131 ms	219428 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1744 ms	156864 KB	Output is correct
7	Correct	808 ms	60316 KB	Output is correct
8	Correct	1756 ms	156768 KB	Output is correct
9	Incorrect	2090 ms	139480 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1065 ms	102068 KB	Output is correct
3	Correct	2168 ms	219404 KB	Output is correct
4	Correct	2131 ms	219428 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	131 ms	12840 KB	Output is correct
7	Incorrect	146 ms	14012 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	50 ms	5076 KB	Output is correct
3	Correct	61 ms	5084 KB	Output is correct
4	Correct	1215 ms	74384 KB	Output is correct
5	Correct	71 ms	5056 KB	Output is correct
6	Correct	67 ms	5052 KB	Output is correct
7	Correct	86 ms	5072 KB	Output is correct
8	Correct	105 ms	6052 KB	Output is correct
9	Correct	81 ms	6072 KB	Output is correct
10	Correct	54 ms	5068 KB	Output is correct
11	Correct	47 ms	5080 KB	Output is correct
12	Correct	47 ms	5056 KB	Output is correct
13	Correct	75 ms	5056 KB	Output is correct
14	Correct	631 ms	40644 KB	Output is correct
15	Correct	51 ms	5080 KB	Output is correct
16	Correct	558 ms	40644 KB	Output is correct
17	Correct	976 ms	71760 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	7 ms	944 KB	Output is correct
3	Correct	6 ms	916 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Incorrect	1 ms	212 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Submission #545378

Compilation message