oj.uz

답안 #200450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200450 2020-02-06T20:48:07 Z extraterrestrial 이상한 기계 (APIO19_strange_device) C++14
0 / 100
 5 ms 380 KB 
#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;
}

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 = 1;
		a = 123;
		b = rnd() % a;
		//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)) % 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 && 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(x) << ' ' << y2 << '\n';
				have[get_num(x2)].pb({0ll, -1ll});
				have[get_num(x2)].pb({y2 + 1, 1ll});
			}
			if (tl > tr) {
				continue;
			}
			tr += b - 1;
			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 = (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 (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);
		}
		/*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';	
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:99:8: warning: unused variable 'f' [-Wunused-variable]
    int f = get_num((tl + tl / b) % a), s = get_num((tr + tr / b) % a), cnt = (tr - tl + 1) / b;
        ^
strange_device.cpp:99:40: warning: unused variable 's' [-Wunused-variable]
    int f = get_num((tl + tl / b) % a), s = get_num((tr + tr / b) % a), cnt = (tr - tl + 1) / b;
                                        ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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