oj.uz

답안 #545359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545359 2022-04-04T10:51:43 Z amunduzbaev 이상한 기계 (APIO19_strange_device) C++17
0 / 100
 1161 ms 101976 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 x = (bl + 1) * B, c = (br - bl - 1);
			if(c){
				a.push_back({(x + x/B) % 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;
	for(auto& x : a){
		x[0] = (i128)x[0] * (i128)bp(D, A - 2, A) % A;
		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] = max(x[1], r);
	}
	
	sort(ss.begin(), ss.end());
	map<int, int> mm;
	for(auto& x : ss){
		//~ x[2] = (x[2] - x[0] % A + A) % A;
		auto it = lower_bound(tot.begin(), tot.end(), (ar<int, 2>){x[2] + 1, -1});
		if(it != tot.begin()){
			it--;
			if(x[2] <= (*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] - 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 Incorrect 6 ms 916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 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 Incorrect 1161 ms 101976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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