oj.uz

Submission #200449

# Submission time Handle Problem Language Result Execution time Memory
200449 2020-02-06T20:35:00 Z extraterrestrial Strange Device (APIO19_strange_device) C++14
25 / 100
 1366 ms 104824 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(time(0));
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);
	int n = 1;
	a = 10;
	b = 1;
	cin >> n >> a >> b;
	vector<pair<int, int>> q(n);
	int lim = 1e6;	
	for (auto &it : q) {
		cin >> it.F >> it.S;
		//it.F = rnd() % 20;
		//it.S = it.F + rnd() % 20;
	}
	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 && 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;
		}
		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';
	}*/
	cout << ans << '\n';	
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:98:7: 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:98:39: 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;
                                       ^
strange_device.cpp:58:6: warning: unused variable 'lim' [-Wunused-variable]
  int lim = 1e6; 
      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 11 ms 1016 KB Output is correct
3 Correct 11 ms 888 KB Output is correct
4 Incorrect 5 ms 380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 6 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Incorrect 811 ms 49132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Incorrect 811 ms 49132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Incorrect 811 ms 49132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 66 ms 5496 KB Output is correct
3 Correct 68 ms 5496 KB Output is correct
4 Correct 1366 ms 104824 KB Output is correct
5 Correct 79 ms 6904 KB Output is correct
6 Correct 76 ms 6520 KB Output is correct
7 Correct 79 ms 6776 KB Output is correct
8 Correct 109 ms 10464 KB Output is correct
9 Correct 102 ms 10744 KB Output is correct
10 Correct 65 ms 5240 KB Output is correct
11 Correct 71 ms 5364 KB Output is correct
12 Correct 61 ms 5624 KB Output is correct
13 Correct 83 ms 8312 KB Output is correct
14 Correct 570 ms 48504 KB Output is correct
15 Correct 67 ms 5756 KB Output is correct
16 Correct 633 ms 47988 KB Output is correct
17 Correct 1216 ms 98552 KB Output is correct
18 Correct 5 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 11 ms 1016 KB Output is correct
3 Correct 11 ms 888 KB Output is correct
4 Incorrect 5 ms 380 KB Output isn't correct
5 Halted 0 ms 0 KB -