Submission #684824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684824	2023-01-22T14:20:50 Z	vovamr	Strange Device (APIO19_strange_device)	C++17	65 / 100	628 ms	62536 KB

strange_device

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 4e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	ll n, a, b;
	cin >> n >> a >> b;

	ll T;

	ll g = gcd(a, b + 1);
	ll f = a / g;
	if (f > inf / b) T = inf;
	else T = f * b;

	ve<pll> ev;
	for (int i = 0; i < n; ++i) {
		ll l, r;
		cin >> l >> r;

		l %= T, r %= T;

		if (l <= r) {
			ev.pb({l, +1});
			ev.pb({r + 1, -1});
		}
		else {
			ev.pb({0, +1});
			ev.pb({r + 1, -1});

			ev.pb({l, +1});
			ev.pb({T, -1});
		}
	}

	sort(all(ev));

	ll ans = 0, sum = 0;
	for (int i = 0; i < sz(ev); ) {
		int j = i;
		ll prev = (!i ? 0 : ev[i - 1].fi);
		if (sum > 0) ans += (ev[i].fi - prev);

		while (j < sz(ev) && ev[j].fi == ev[i].fi) {
			sum += ev[j].se;
			++j;
		}
		i = j;
	}

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	6 ms	984 KB	Output is correct
3	Correct	5 ms	912 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	5 ms	856 KB	Output is correct
17	Correct	53 ms	4480 KB	Output is correct
18	Correct	0 ms	296 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	345 ms	33236 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	463 ms	33192 KB	Output is correct
3	Correct	551 ms	62536 KB	Output is correct
4	Correct	517 ms	43028 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	463 ms	33192 KB	Output is correct
3	Correct	551 ms	62536 KB	Output is correct
4	Correct	517 ms	43028 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	549 ms	51336 KB	Output is correct
7	Correct	497 ms	48772 KB	Output is correct
8	Correct	549 ms	44216 KB	Output is correct
9	Correct	628 ms	44208 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	463 ms	33192 KB	Output is correct
3	Correct	551 ms	62536 KB	Output is correct
4	Correct	517 ms	43028 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	55 ms	7228 KB	Output is correct
7	Correct	53 ms	7224 KB	Output is correct
8	Correct	49 ms	7240 KB	Output is correct
9	Correct	53 ms	7388 KB	Output is correct
10	Correct	52 ms	7240 KB	Output is correct
11	Correct	50 ms	7268 KB	Output is correct
12	Correct	46 ms	7252 KB	Output is correct
13	Correct	53 ms	7220 KB	Output is correct
14	Correct	47 ms	7288 KB	Output is correct
15	Correct	63 ms	7296 KB	Output is correct
16	Correct	57 ms	7228 KB	Output is correct
17	Correct	49 ms	7176 KB	Output is correct
18	Correct	501 ms	44696 KB	Output is correct
19	Correct	482 ms	44436 KB	Output is correct
20	Correct	592 ms	44864 KB	Output is correct
21	Correct	57 ms	7232 KB	Output is correct
22	Correct	44 ms	7200 KB	Output is correct
23	Correct	140 ms	26612 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	55 ms	4464 KB	Output is correct
3	Correct	52 ms	4572 KB	Output is correct
4	Correct	609 ms	33244 KB	Output is correct
5	Correct	53 ms	7228 KB	Output is correct
6	Correct	53 ms	7228 KB	Output is correct
7	Correct	53 ms	7204 KB	Output is correct
8	Correct	63 ms	7296 KB	Output is correct
9	Correct	53 ms	7248 KB	Output is correct
10	Correct	62 ms	7248 KB	Output is correct
11	Correct	56 ms	7272 KB	Output is correct
12	Correct	47 ms	7236 KB	Output is correct
13	Correct	57 ms	7276 KB	Output is correct
14	Correct	601 ms	44752 KB	Output is correct
15	Correct	56 ms	7232 KB	Output is correct
16	Correct	505 ms	52328 KB	Output is correct
17	Correct	532 ms	52424 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	6 ms	984 KB	Output is correct
3	Correct	5 ms	912 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	5 ms	856 KB	Output is correct
17	Correct	53 ms	4480 KB	Output is correct
18	Correct	0 ms	296 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #684824

Compilation message