Submission #684823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684823	2023-01-22T14:19:00 Z	vovamr	Strange Device (APIO19_strange_device)	C++17	5 / 100	676 ms	44648 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() {
	int 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{{T, -inf}};
	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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	6 ms	1240 KB	Output is correct
3	Correct	6 ms	1240 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	324 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	6 ms	1236 KB	Output is correct
17	Correct	58 ms	7232 KB	Output is correct
18	Runtime error	1 ms	456 KB	Execution killed with signal 8
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	359 ms	40124 KB	Output is correct

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	543 ms	42540 KB	Output is correct
3	Runtime error	1 ms	468 KB	Execution killed with signal 8
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	543 ms	42540 KB	Output is correct
3	Runtime error	1 ms	468 KB	Execution killed with signal 8
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	543 ms	42540 KB	Output is correct
3	Runtime error	1 ms	468 KB	Execution killed with signal 8
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	324 KB	Output is correct
2	Correct	58 ms	7212 KB	Output is correct
3	Correct	53 ms	7192 KB	Output is correct
4	Correct	676 ms	44648 KB	Output is correct
5	Incorrect	10 ms	4556 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	6 ms	1240 KB	Output is correct
3	Correct	6 ms	1240 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	324 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	6 ms	1236 KB	Output is correct
17	Correct	58 ms	7232 KB	Output is correct
18	Runtime error	1 ms	456 KB	Execution killed with signal 8
19	Halted	0 ms	0 KB	-

Submission #684823

Compilation message