Submission #167544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167544	2019-12-08T22:25:41 Z	qkxwsm	Strange Device (APIO19_strange_device)	C++14	100 / 100	1253 ms	100408 KB

strange_device

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

typedef __int128_t ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

ll gcd(ll a, ll b)
{
	return (b == 0 ? a : gcd(b, a % b));
}
void readi(ll &x)
{
	long long res;
	cin >> res;
	x = res;
}

int Q;
ll A, B;
ll period, ans;
vpl events;

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(12);
	cerr << fixed << setprecision(4);
	cin >> Q;
	readi(A); readi(B);
	ll g = gcd(A, B + 1);
	period = B * A / g;
	while(Q--)
	{
		ll L, R;
		readi(L); readi(R);
		if (R - L + 1 >= period)
		{
			cout << (long long) period << '\n';
			return 0;
		}
		L %= period;
		R %= period;
		if (L > R)
		{
			events.PB({L, 1});
			events.PB({period, -1});
			events.PB({0, 1});
			events.PB({R + 1, -1});
		}
		else
		{
			events.PB({L, 1});
			events.PB({R + 1, -1});
		}
	}
	sort(ALL(events));
	int sum = 0;
	FOR(i, 0, SZ(events))
	{
		if (sum)
		{
			ans += (events[i].fi - events[i - 1].fi);
		}
		sum += events[i].se;
	}
	cout << (long long) ans << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	10 ms	1928 KB	Output is correct
3	Correct	11 ms	1908 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	264 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	10 ms	1908 KB	Output is correct
17	Correct	100 ms	11360 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	900 ms	100332 KB	Output is correct
3	Correct	930 ms	100408 KB	Output is correct
4	Correct	901 ms	99960 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	900 ms	100332 KB	Output is correct
3	Correct	930 ms	100408 KB	Output is correct
4	Correct	901 ms	99960 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	927 ms	100132 KB	Output is correct
7	Correct	937 ms	99604 KB	Output is correct
8	Correct	916 ms	99676 KB	Output is correct
9	Correct	1071 ms	99820 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	900 ms	100332 KB	Output is correct
3	Correct	930 ms	100408 KB	Output is correct
4	Correct	901 ms	99960 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	86 ms	11364 KB	Output is correct
7	Correct	91 ms	11356 KB	Output is correct
8	Correct	89 ms	11360 KB	Output is correct
9	Correct	92 ms	11360 KB	Output is correct
10	Correct	83 ms	11364 KB	Output is correct
11	Correct	91 ms	11364 KB	Output is correct
12	Correct	83 ms	11360 KB	Output is correct
13	Correct	97 ms	11316 KB	Output is correct
14	Correct	86 ms	11356 KB	Output is correct
15	Correct	101 ms	11360 KB	Output is correct
16	Correct	97 ms	11364 KB	Output is correct
17	Correct	90 ms	11360 KB	Output is correct
18	Correct	936 ms	99776 KB	Output is correct
19	Correct	897 ms	99880 KB	Output is correct
20	Correct	1161 ms	99708 KB	Output is correct
21	Correct	102 ms	11364 KB	Output is correct
22	Correct	80 ms	11360 KB	Output is correct
23	Correct	260 ms	43200 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	95 ms	11364 KB	Output is correct
3	Correct	96 ms	11364 KB	Output is correct
4	Correct	1253 ms	100020 KB	Output is correct
5	Correct	97 ms	11360 KB	Output is correct
6	Correct	98 ms	11356 KB	Output is correct
7	Correct	98 ms	11360 KB	Output is correct
8	Correct	101 ms	11360 KB	Output is correct
9	Correct	94 ms	11360 KB	Output is correct
10	Correct	100 ms	11360 KB	Output is correct
11	Correct	96 ms	11360 KB	Output is correct
12	Correct	87 ms	11360 KB	Output is correct
13	Correct	101 ms	11360 KB	Output is correct
14	Correct	1137 ms	100052 KB	Output is correct
15	Correct	134 ms	11360 KB	Output is correct
16	Correct	865 ms	76424 KB	Output is correct
17	Correct	902 ms	76060 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct

Subtask #8
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	10 ms	1928 KB	Output is correct
3	Correct	11 ms	1908 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	264 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	10 ms	1908 KB	Output is correct
17	Correct	100 ms	11360 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Correct	2 ms	504 KB	Output is correct
27	Correct	3 ms	504 KB	Output is correct
28	Correct	660 ms	88408 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	900 ms	100332 KB	Output is correct
31	Correct	930 ms	100408 KB	Output is correct
32	Correct	901 ms	99960 KB	Output is correct
33	Correct	2 ms	376 KB	Output is correct
34	Correct	927 ms	100132 KB	Output is correct
35	Correct	937 ms	99604 KB	Output is correct
36	Correct	916 ms	99676 KB	Output is correct
37	Correct	1071 ms	99820 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	86 ms	11364 KB	Output is correct
40	Correct	91 ms	11356 KB	Output is correct
41	Correct	89 ms	11360 KB	Output is correct
42	Correct	92 ms	11360 KB	Output is correct
43	Correct	83 ms	11364 KB	Output is correct
44	Correct	91 ms	11364 KB	Output is correct
45	Correct	83 ms	11360 KB	Output is correct
46	Correct	97 ms	11316 KB	Output is correct
47	Correct	86 ms	11356 KB	Output is correct
48	Correct	101 ms	11360 KB	Output is correct
49	Correct	97 ms	11364 KB	Output is correct
50	Correct	90 ms	11360 KB	Output is correct
51	Correct	936 ms	99776 KB	Output is correct
52	Correct	897 ms	99880 KB	Output is correct
53	Correct	1161 ms	99708 KB	Output is correct
54	Correct	102 ms	11364 KB	Output is correct
55	Correct	80 ms	11360 KB	Output is correct
56	Correct	260 ms	43200 KB	Output is correct
57	Correct	2 ms	376 KB	Output is correct
58	Correct	95 ms	11364 KB	Output is correct
59	Correct	96 ms	11364 KB	Output is correct
60	Correct	1253 ms	100020 KB	Output is correct
61	Correct	97 ms	11360 KB	Output is correct
62	Correct	98 ms	11356 KB	Output is correct
63	Correct	98 ms	11360 KB	Output is correct
64	Correct	101 ms	11360 KB	Output is correct
65	Correct	94 ms	11360 KB	Output is correct
66	Correct	100 ms	11360 KB	Output is correct
67	Correct	96 ms	11360 KB	Output is correct
68	Correct	87 ms	11360 KB	Output is correct
69	Correct	101 ms	11360 KB	Output is correct
70	Correct	1137 ms	100052 KB	Output is correct
71	Correct	134 ms	11360 KB	Output is correct
72	Correct	865 ms	76424 KB	Output is correct
73	Correct	902 ms	76060 KB	Output is correct
74	Correct	2 ms	376 KB	Output is correct
75	Correct	2 ms	376 KB	Output is correct
76	Correct	2 ms	376 KB	Output is correct
77	Correct	2 ms	376 KB	Output is correct
78	Correct	2 ms	416 KB	Output is correct
79	Correct	10 ms	1908 KB	Output is correct
80	Correct	1241 ms	78232 KB	Output is correct
81	Correct	1245 ms	77812 KB	Output is correct
82	Correct	1053 ms	100320 KB	Output is correct
83	Correct	1048 ms	81224 KB	Output is correct
84	Correct	1094 ms	99800 KB	Output is correct
85	Correct	1132 ms	80948 KB	Output is correct
86	Correct	260 ms	43200 KB	Output is correct
87	Correct	2 ms	376 KB	Output is correct

Submission #167544

Compilation message