oj.uz

Submission #210740

# Submission time Handle Problem Language Result Execution time Memory
210740 2020-03-18T09:41:52 Z islingr Strange Device (APIO19_strange_device) C++14
35 / 100
 2323 ms 32240 KB 
/*
	22/02/2020
	islingr
*/

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

#define all(x) begin(x), end(x)
#define eb(x...) emplace_back(x)

using ll = int64_t;

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

struct event {
	ll l, r;
	event(ll a, ll b) : l{a}, r{b} { }
	bool operator<(const event &e) const { return r < e.r; }
};

ll solve () {
	int n; ll a, b; cin >> n >> a >> b;
	ll g = __gcd(a, b + 1), p = a / g * b;
	vector<event> v; v.reserve(2 * n);
	rep(i, 0, n) {
		ll l, r; cin >> l >> r;
		if (r - l + 1 < p) {
			l %= p; r %= p;
			if (l <= r) v.eb(l, r);
			else v.eb(0, r), v.eb(l, p - 1);
		} else return p;
	}
	sort(all(v));
	ll ans = 0;
	while (!v.empty()) {
		event top = v.back(); v.pop_back();
		while (!v.empty() && top.l <= v.back().r) {
			ckmin(top.l, v.back().l);
			v.pop_back();
		}
		ans += top.r - top.l + 1;
	}
	return ans;
}

signed main() {
	cout << solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 27 ms 888 KB Output is correct
3 Correct 27 ms 888 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 128 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 26 ms 888 KB Output is correct
17 Correct 228 ms 5556 KB Output is correct
18 Incorrect 5 ms 256 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Incorrect 5 ms 256 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 1525 ms 23672 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 2166 ms 31032 KB Output is correct
3 Correct 2157 ms 32056 KB Output is correct
4 Correct 2137 ms 27128 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 2166 ms 31032 KB Output is correct
3 Correct 2157 ms 32056 KB Output is correct
4 Correct 2137 ms 27128 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 2180 ms 27128 KB Output is correct
7 Correct 2146 ms 27256 KB Output is correct
8 Correct 2190 ms 27232 KB Output is correct
9 Correct 2269 ms 27128 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 2166 ms 31032 KB Output is correct
3 Correct 2157 ms 32056 KB Output is correct
4 Correct 2137 ms 27128 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 226 ms 5624 KB Output is correct
7 Correct 230 ms 5540 KB Output is correct
8 Correct 226 ms 5624 KB Output is correct
9 Correct 222 ms 5624 KB Output is correct
10 Correct 221 ms 5624 KB Output is correct
11 Correct 226 ms 5600 KB Output is correct
12 Correct 244 ms 5608 KB Output is correct
13 Correct 227 ms 5728 KB Output is correct
14 Correct 223 ms 5624 KB Output is correct
15 Correct 226 ms 5624 KB Output is correct
16 Correct 229 ms 5624 KB Output is correct
17 Correct 225 ms 5564 KB Output is correct
18 Correct 2304 ms 27256 KB Output is correct
19 Correct 2220 ms 27236 KB Output is correct
20 Correct 2323 ms 30048 KB Output is correct
21 Correct 272 ms 5624 KB Output is correct
22 Correct 257 ms 5604 KB Output is correct
23 Correct 770 ms 18196 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 229 ms 5680 KB Output is correct
3 Correct 252 ms 5628 KB Output is correct
4 Correct 2323 ms 27228 KB Output is correct
5 Correct 231 ms 5624 KB Output is correct
6 Correct 231 ms 5624 KB Output is correct
7 Correct 235 ms 5624 KB Output is correct
8 Correct 226 ms 5624 KB Output is correct
9 Correct 275 ms 5624 KB Output is correct
10 Correct 244 ms 5624 KB Output is correct
11 Correct 226 ms 5624 KB Output is correct
12 Correct 245 ms 5624 KB Output is correct
13 Correct 227 ms 5624 KB Output is correct
14 Correct 2236 ms 32240 KB Output is correct
15 Correct 224 ms 5624 KB Output is correct
16 Correct 2189 ms 30328 KB Output is correct
17 Correct 2183 ms 28792 KB Output is correct
18 Incorrect 5 ms 364 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 27 ms 888 KB Output is correct
3 Correct 27 ms 888 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 128 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 26 ms 888 KB Output is correct
17 Correct 228 ms 5556 KB Output is correct
18 Incorrect 5 ms 256 KB Output isn't correct