Submission #200448

#	Time	Username	Problem	Language	Result	Execution time	Memory
200448		extraterrestrial	이상한 기계 (APIO19_strange_device)	C++14	20 / 100	1402 ms	126280 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define int ll

int k, in_group, groups, a, b;

int get_num(int x) {
	int id = x % groups;
	return in_group * id + (x - id) / groups;
}

int scanline(vector<pair<int, int>> &ev) {
	sort(all(ev));
	int cl = -1, balance = 0, res = 0;
	for (auto it : ev) {
		balance -= it.S;
		if (balance == 0) {
			res += it.F - cl;
			cl = -1;
		}
		else {
			if (cl == -1) {
				cl = it.F;
			} 
		}
	}
	return res;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n >> a >> b;
	groups = __gcd(a, b + 1);
	in_group = a / groups;
	//cout << groups << ' ' << in_group << '\n';
	map<int, vector<pair<int, int>>> have;
	vector<pair<int, int>> ev;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		int tl = (l % b == 0 ? l : l + (b - l % b)), tr = (r % b == b - 1 ? r : r - r % b - 1);
		int x = ((l - l % b) + ((l - l % b) / b)) % a, y = l % b,  
		x2 = ((r - r % b) + ((r - r % b) / b)) % a, y2 = r % b;
		//cout << i << ' ' << tl << ' ' << tr << '\n';
		tr -= b - 1;
		if (tl > tr && y <= y2) {
			//cout << "C0 " << get_num(x) << ' ' << y << ' ' << y2 << '\n';
			have[get_num(x)].pb({y, -1ll});
			have[get_num(x)].pb({y2 + 1, 1ll});
			continue;
		}
		//cout << "OK " << i << '\n';	
		if (tl > l) {
			//cout << "C1 " << get_num(x) << ' ' << y << '\n';
			have[get_num(x)].pb({y, -1ll});
			have[get_num(x)].pb({b, 1ll});
		}
		if (tr < r) {
			//cout << "C2 " << get_num(x) << ' ' << y2 << '\n';
			have[get_num(x2)].pb({0ll, -1ll});
			have[get_num(x2)].pb({y2 + 1, 1ll});
		}

		if (tl > tr) {
			continue;
		}
		int cx = (tl + tl / b) % a, id = cx % groups, num_in_group = (cx - id) / groups;
		int f = get_num((tl + tl / b) % a), s = get_num((tr + tr / b) % a), cnt;
		//cout << i << ' ' << (tl + tl / b) % a << ' ' << (tr + tr / b) % a << ' ' <<  f << ' ' << s << '\n';
		if (f <= s) {
			cnt = s - f + 1;
		}
		else {
			cnt = in_group - (s - f - 1); 
		}
		//cout << "MAIN_C " << f << ' ' << cnt << ' ' << id << ' ' << num_in_group << ' ' << get_num(cx) << '\n';
		if (num_in_group + cnt - 1 < in_group) {
			ev.pb({get_num(cx), -1});
			ev.pb({get_num(cx) + cnt, 1});
		}
		else {
			ev.pb({get_num(cx), -1});
			ev.pb({get_num(cx) - num_in_group + in_group, 1});
			cnt -= in_group - num_in_group;
			ev.pb({get_num(cx) - num_in_group, -1});
			ev.pb({get_num(cx) - num_in_group + cnt, 1});
		}
	}
	sort(all(ev));
	/*for (auto it : ev) {
		cout << "DB " << it.F << ' ' << it.S << '\n';
	}*/
	int balance = 0, cl = -1, ans = 0;
	for (auto it : ev) {
		balance -= it.S;
		if (balance == 0) {
			while (!have.empty() && have.begin()->F < it.F) {
				have.erase(have.begin());
			}
			ans += (it.F - cl) * b;
			cl = -1;
		}
		else if (balance > 0 && cl == -1) {
			while (!have.empty() && have.begin()->F < it.F) {
				ans += scanline(have.begin()->S);
				have.erase(have.begin());
			}
			cl = it.F;
		}
	}
	//cout << ans << '\n';
	for (auto it : have) {
		ans += scanline(it.S);
	}
	cout << ans << '\n';	
}

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