oj.uz

Submission #545377

# Submission time Handle Problem Language Result Execution time Memory
545377 2022-04-04T11:55:25 Z amunduzbaev Strange Device (APIO19_strange_device) C++17
30 / 100
 2119 ms 219484 KB 
#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 = 1;
	if(!a.empty()){
		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 1 ms 212 KB Output is correct
2 Correct 8 ms 916 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 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1062 ms 102164 KB Output is correct
3 Correct 2119 ms 219428 KB Output is correct
4 Correct 2027 ms 219484 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 1062 ms 102164 KB Output is correct
3 Correct 2119 ms 219428 KB Output is correct
4 Correct 2027 ms 219484 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1791 ms 156776 KB Output is correct
7 Correct 809 ms 60364 KB Output is correct
8 Correct 1729 ms 156992 KB Output is correct
9 Incorrect 2087 ms 139444 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 1062 ms 102164 KB Output is correct
3 Correct 2119 ms 219428 KB Output is correct
4 Correct 2027 ms 219484 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 153 ms 12752 KB Output is correct
7 Incorrect 152 ms 13952 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 1 ms 212 KB Output is correct
2 Correct 55 ms 5084 KB Output is correct
3 Correct 63 ms 5056 KB Output is correct
4 Correct 1154 ms 74388 KB Output is correct
5 Correct 67 ms 5068 KB Output is correct
6 Correct 66 ms 5064 KB Output is correct
7 Correct 68 ms 5072 KB Output is correct
8 Correct 83 ms 5960 KB Output is correct
9 Correct 81 ms 6116 KB Output is correct
10 Correct 60 ms 5080 KB Output is correct
11 Correct 51 ms 5080 KB Output is correct
12 Correct 47 ms 5056 KB Output is correct
13 Correct 70 ms 5128 KB Output is correct
14 Correct 624 ms 40664 KB Output is correct
15 Correct 52 ms 5056 KB Output is correct
16 Correct 540 ms 40644 KB Output is correct
17 Correct 970 ms 71872 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 1 ms 212 KB Output is correct
2 Correct 8 ms 916 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 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -