제출 #200459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
200459		extraterrestrial	이상한 기계 (APIO19_strange_device)	C++14	100 / 100	1966 ms	241336 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) {
	return (x / (b + 1)) % in_group;
}

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;
}

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int slow_solve(int n, int a, int b, vector<pair<int, int>> q) {
	set<pair<int, int>> used;
	for (auto it : q) {
		for (int i = it.F; i <= it.S; i++) {
			int x = (i + i / b) % a, y = i % b;
			used.insert({x, y});
		}
	}
	return SZ(used);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//while (true) {
		int n = 5;
		a = 123;
		b = rnd() % a;
		if (b <= 0) {
			b = 1;
		}
		//cout << n << ' ' << a << ' ' << b << endl;
		cin >> n >> a >> b;
		vector<pair<int, int>> q(n);
		int lim = 10;	
		for (auto &it : q) {
			cin >> it.F >> it.S;
			//it.F = rnd() % lim;
			//it.S = it.F + rnd() % lim;
		}
		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 = q[i].F, r = q[i].S;
			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), y = l % b,  
			x2 = (r - r % b) + ((r - r % b) / b), y2 = r % b;
			//cout << i << ' ' << tl << ' ' << tr << '\n';
			//tr -= b - 1;
			if (tl > tr && x == x2) {
				//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(x2) << ' ' << y2 << '\n';
				have[get_num(x2)].pb({0ll, -1ll});
				have[get_num(x2)].pb({y2 + 1, 1ll});
			}	
			if (tl > tr) {
				continue;
			}
			//cout << tl << ' ' << tr << '\n';
			//tr += b - 1;
			int cx = (tl + tl / b);
			int f = get_num(cx), s = get_num((tr + tr / b)), cnt = (tr - tl + 1) / b;
			//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); 
			}*/
			cnt = min(cnt, in_group);
			//cout << "MAIN_C " << f << ' ' << cnt << ' ' << id << ' ' << num_in_group << ' ' << get_num(cx) << '\n';
			if (get_num(cx) + cnt - 1 < in_group) {
				ev.pb({get_num(cx), -1});
				ev.pb({get_num(cx) + cnt, 1});
				//cout << get_num(cx) << ' ' << get_num(cx) + cnt << '\n';
			}
			else {
				ev.pb({get_num(cx), -1});
				ev.pb({in_group, 1});
				cnt -= in_group - get_num(cx);
				ev.pb({0, -1});
				ev.pb({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) {
			//cout << "DB " << it.F << '\n';
			ans += scanline(it.S);
		}
		/*if (ans != slow_solve(n, a, b, q)) {
			cout << "ERROR\n";
			cout << n << ' ' << a << ' ' << b << '\n';
			for (auto it : q) {
				cout << it.F << ' ' << it.S << '\n';
			}
			cout << ans << ' ' << slow_solve(n, a, b, q) << '\n';
			cout << '\n';
			exit(0);
		}*/	
	//}
	
	cout << ans << '\n';	
}
		

컴파일 시 표준 에러 (stderr) 메시지

strange_device.cpp: In function 'int main()':
strange_device.cpp:103:8: warning: unused variable 'f' [-Wunused-variable]
    int f = get_num(cx), s = get_num((tr + tr / b)), cnt = (tr - tl + 1) / b;
        ^
strange_device.cpp:103:25: warning: unused variable 's' [-Wunused-variable]
    int f = get_num(cx), s = get_num((tr + tr / b)), cnt = (tr - tl + 1) / b;
                         ^
strange_device.cpp:62:7: warning: unused variable 'lim' [-Wunused-variable]
   int lim = 10; 
       ^~~

• 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