oj.uz

Submission #545371

# Submission time Handle Problem Language Result Execution time Memory
545371 2022-04-04T11:28:14 Z amunduzbaev Strange Device (APIO19_strange_device) C++17
30 / 100
 2116 ms 219512 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;
}

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*B + bl) % A / G});
		} else {
			ss.push_back({l % B, B - 1, (bl*B + bl) % A / G});
			ss.push_back({0, r % B, (br*B + br) % A / G});
			int c = (br - bl - 1);
			if(c){
				a.push_back({((bl+1)*(B+1)) % 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])){
			res += (x[1] - x[0] + 1), mm[x[2]] = x[1];
		} else if(mm[x[2]] < x[1]) res += (x[1] - max(x[0] - 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 6 ms 928 KB Output is correct
3 Correct 6 ms 1300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 316 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 284 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 989 ms 102048 KB Output is correct
3 Correct 1968 ms 219388 KB Output is correct
4 Correct 1851 ms 219512 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 989 ms 102048 KB Output is correct
3 Correct 1968 ms 219388 KB Output is correct
4 Correct 1851 ms 219512 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1741 ms 156968 KB Output is correct
7 Correct 863 ms 60588 KB Output is correct
8 Correct 1717 ms 156928 KB Output is correct
9 Incorrect 2116 ms 139572 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 989 ms 102048 KB Output is correct
3 Correct 1968 ms 219388 KB Output is correct
4 Correct 1851 ms 219512 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 141 ms 12780 KB Output is correct
7 Incorrect 151 ms 17640 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 52 ms 5080 KB Output is correct
3 Correct 72 ms 8776 KB Output is correct
4 Correct 1223 ms 111768 KB Output is correct
5 Correct 83 ms 8804 KB Output is correct
6 Correct 81 ms 8780 KB Output is correct
7 Correct 81 ms 9024 KB Output is correct
8 Correct 90 ms 9664 KB Output is correct
9 Correct 92 ms 9840 KB Output is correct
10 Correct 62 ms 8768 KB Output is correct
11 Correct 54 ms 8776 KB Output is correct
12 Correct 50 ms 8768 KB Output is correct
13 Correct 83 ms 8880 KB Output is correct
14 Correct 673 ms 77884 KB Output is correct
15 Correct 57 ms 8808 KB Output is correct
16 Correct 551 ms 77916 KB Output is correct
17 Correct 1056 ms 108956 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 6 ms 928 KB Output is correct
3 Correct 6 ms 1300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 316 KB Output isn't correct
7 Halted 0 ms 0 KB -