oj.uz

답안 #545393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545393 2022-04-04T12:26:17 Z amunduzbaev 이상한 기계 (APIO19_strange_device) C++17
25 / 100
 2008 ms 204664 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});
		} else {
			ss.push_back({l % B, B - 1, (bl*D) % A});
			ss.push_back({0, r % B, (br*D) % A});
			int c = (br - bl - 1);
			if(c){
				a.push_back({((bl+1)*D) % A, c});
			}
		}
	}
	
	for(auto x : ss) assert(x[2] % G == 0), x[2] /= G;
	for(auto x : a) assert(x[0] % G == 0), x[0] /= G;
	
	A /= G, D /= G;
	int res = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 916 KB Output is correct
3 Correct 8 ms 944 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 256 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1104 ms 102000 KB Output is correct
3 Incorrect 2008 ms 204664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1104 ms 102000 KB Output is correct
3 Incorrect 2008 ms 204664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1104 ms 102000 KB Output is correct
3 Incorrect 2008 ms 204664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 54 ms 5060 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 1135 ms 74368 KB Output is correct
5 Correct 80 ms 5040 KB Output is correct
6 Correct 67 ms 5084 KB Output is correct
7 Correct 66 ms 5092 KB Output is correct
8 Correct 79 ms 5960 KB Output is correct
9 Correct 76 ms 6084 KB Output is correct
10 Correct 60 ms 5076 KB Output is correct
11 Correct 48 ms 5088 KB Output is correct
12 Correct 47 ms 5068 KB Output is correct
13 Correct 71 ms 5064 KB Output is correct
14 Correct 609 ms 40656 KB Output is correct
15 Correct 51 ms 5076 KB Output is correct
16 Correct 539 ms 40644 KB Output is correct
17 Correct 945 ms 71700 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 916 KB Output is correct
3 Correct 8 ms 944 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 -