Submission #545325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545325	2022-04-04T09:11:17 Z	amunduzbaev	Strange Device (APIO19_strange_device)	C++17	0 / 100	1379 ms	125580 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;
}

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>> big;
	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});
		} else {
			ss.push_back({l % B, B - 1, (bl*B + bl) % A});
			ss.push_back({0, r % B, (br*B + br) % A});
			int x = (bl + 1) * B, c = (br - bl - 1);
			if(c){
				big.push_back({(x + x/B) % A, c});
			}
		}
	}
	
	sort(big.begin(), big.end(), [&](auto& a, auto& b){
		return (a[0] % G < b[0] % G);
	});
	sort(ss.begin(), ss.end(), [&](auto& a, auto& b){
		return (a[2] % G < b[2] % G);
	});
	int res = 0;
	
	auto just = [&](vector<ar<int, 3>>& ss, int A){
		sort(ss.begin(), ss.end());
		map<int, int> mm;
		for(auto& x : ss){ x[2] /= G;
			//~ x[2] = (x[2] - x[0] % A + A) % A;
			
			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];
		}
	};
	
	auto solve = [&](vector<ar<int, 2>>& a, vector<ar<int, 3>>& ss, int A, int D){
		if(A == 1){
			res += B;
			return;
		}
		
		vector<ar<int, 2>> tot;
		for(auto& x : a){ x[0] /= G;
			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] /= G;
			//~ x[2] = (x[2] - x[0] % A + A) % A;
			auto it = upper_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];
		}
	};
	
	int l = 0, S = ss.size(), Big = big.size();
	for(int i=0;i<Big;){
		int j = i, v = big[i][0]%G;
		vector<ar<int, 2>> tt;
		vector<ar<int, 3>> tmp;
		while(j < Big && big[j][0]%G == v) tt.push_back(big[j]), j++;
		
		while(l < S && ss[l][2]%G < v){
			int j = l;
			while(j < S && ss[j][2]%G == ss[l][2]%G){
				tmp.push_back(ss[j]);
				j++;
			} l = j;
			just(tmp, A / G);
			tmp.clear();
		}
		{
			int j = l;
			while(j < S && ss[j][2]%G == v){
				tmp.push_back(ss[j]);
				j++;
			} l = j;
		}
		solve(tt, tmp, A / G, D / G);
		i = j;
	}
	
	while(l < S){
		int j = l;
		vector<ar<int, 3>> tmp;
		while(j < S && ss[j][0]%G == ss[l][0]%G){
			tmp.push_back(ss[j]);
			j++;
		} l = j;
		just(tmp, A / G);
	}
	
	cout<<res<<"\n";
}

Subtask #1
0 / 10.0

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

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

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
0 / 5.0

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

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1379 ms	125580 KB	Output isn't correct
3	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	Incorrect	1379 ms	125580 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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

Submission #545325

Compilation message