Submission #733173

#	Time	Username	Problem	Language	Result	Execution time	Memory
733173		minhcool	Strange Device (APIO19_strange_device)	C++17	100 / 100	1684 ms	318684 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e6 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

/*
What I'm trying to do:
Just imagine that we want all intervals that begins with (sth, 0) to ((sth + B - 1) % A, B - 1), the rest
has like O(n) segments. Inside this interval, there will be no changes made to t/B
Ez as hell
*/

int n, a, b;

//vector<int> inters[N];
vector<ii> full;
unordered_map<int, int> mp;
bool ok[N];
vector<ii> part[N];

int cnt;

void process(){
	cin >> n >> a >> b;
	int temp = __gcd(a, b + 1);
	for(int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		int temp1 = x / b + 1, temp2 = y / b - 1;
		if(temp1 <= temp2){
			if((temp2 - temp1 + 1) >= a/temp){
				cout << a * b / temp;
				exit(0);
			}
			temp1 %= a/temp, temp2 %= a/temp;
			if(temp1 <= temp2) full.pb({temp1, temp2});
			else{
				full.pb({temp1, a/temp - 1});
				full.pb({0, temp2});
			}
		}
		if((x/b) == (y/b)){
			if(mp.find((x/b) % (a/temp)) == mp.end()){
				cnt++;
				mp[(x/b) % (a/temp)] = cnt;
			}
		//	cout << x << " " << y << " " << cnt << " " << x%b << " " << y%b << "\n";
			part[mp[(x/b) % (a/temp)]].pb({x % b, y % b});	
		}
		else{
			//temp1 = , temp2 = (y / b) * b;
			if(mp.find((x/b) % (a/temp)) == mp.end()){
				cnt++;
				mp[(x/b) % (a/temp)] = cnt;
			}
			part[mp[(x/b) % (a/temp)]].pb({x % b, b - 1});
			//cout << x << " " << y << " " << cnt << " " << x%b << " " << b-1 << "\n";
			if(mp.find((y/b) % (a/temp)) == mp.end()){
				cnt++;
				mp[(y/b) % (a/temp)] = cnt;
			}
			part[mp[(y/b) % (a/temp)]].pb({0, y % b});
		//	cout << x << " " << y << " " << cnt << " " << 0 << " " << y%b << "\n";
		}
	}
	//sort(full.begin(), full.end());
	vector<ii> updates;
	for(auto it : full){
		updates.pb({it.fi, 1});
		updates.pb({it.se + 1, -1});
	}
	for(auto it : mp) updates.pb({it.fi, oo});
	sort(updates.begin(), updates.end());
	int lst = -oo, sum = 0, ans = 0;
	for(auto it : updates){
		if(lst != -oo) ans += b * (it.fi - lst) * (sum != 0);
		lst = it.fi;
		if(abs(it.se) == 1) sum += it.se;
		if(it.se == oo) ok[mp[it.fi]] = (sum == 0);
	}
//	cout << ans << "\n";
//	for(auto it : mp) cout << it.fi << " " << it.se << "\n";
	for(int i = 1; i <= cnt; i++){
		if(!ok[i]) continue;
		//sort(part[i].begin(), part[i].end());
		vector<ii> upds;
		for(auto it : part[i]){
	//		cout << i << " " << it.fi << " " << it.se << "\n";
			upds.pb({it.fi, 1});
			upds.pb({it.se + 1, -1});
		}
		sort(upds.begin(), upds.end());
		int lst = -oo, sum = 0;
		for(auto it : upds){
	//		cout << "OK " << sum << " " << lst << " " << it.fi << "\n";
			if(lst != -oo) ans += (it.fi - lst) * (sum != 0);
			sum += it.se;
			lst = it.fi;
		}
	//	cout << ans << "\n";
	}
	cout << ans << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("device.inp", "r", stdin);
	//freopen("device.out", "w", stdout);
	process();
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30