Submission #212662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
212662	2020-03-24T03:26:41 Z	vioalbert	Strange Device (APIO19_strange_device)	C++14	65 / 100	570 ms	32684 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, a, b;
pair<ll, ll> t[2000005];
stack<pair<ll, ll>> st;

ll gcd(ll a, ll b) {
	if(b == 0) return a;
	else return gcd(b, a%b);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> a >> b;
	ll g = gcd(a,b+1);
	ll k = a/g;
	ll tlimit = k * b;

	int idx = 0;
	for(int i = 0; i < n; i++) {
		ll l, r; cin >> l >> r;
		l %= tlimit; r %= tlimit;
		if(l > r) {
			t[idx++] = {l, tlimit-1};
			t[idx++] = {0, r};
		} else {
			t[idx++] = {l, r};
		}
	}
	sort(t, t+idx);

	st.push(t[0]);
	for(int i = 1; i < idx; i++) {
		if(st.top().second < t[i].first)
			st.push(t[i]);
		else if(st.top().second < t[i].second)
			st.top().second = t[i].second; 
	}

	ll ans = 0;
	while(!st.empty()) {
		ans += 1ll * (st.top().second - st.top().first + 1);
		st.pop();
	}

	cout << ans << '\n';

	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	10 ms	1016 KB	Output is correct
3	Correct	12 ms	1152 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	4 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	4 ms	384 KB	Output is correct
15	Correct	4 ms	384 KB	Output is correct
16	Correct	9 ms	1024 KB	Output is correct
17	Correct	57 ms	3960 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Incorrect	5 ms	384 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	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	360 ms	16032 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	515 ms	32532 KB	Output is correct
3	Correct	494 ms	32476 KB	Output is correct
4	Correct	484 ms	32568 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	515 ms	32532 KB	Output is correct
3	Correct	494 ms	32476 KB	Output is correct
4	Correct	484 ms	32568 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	498 ms	32428 KB	Output is correct
7	Correct	498 ms	32404 KB	Output is correct
8	Correct	503 ms	32684 KB	Output is correct
9	Correct	522 ms	32428 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	515 ms	32532 KB	Output is correct
3	Correct	494 ms	32476 KB	Output is correct
4	Correct	484 ms	32568 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	56 ms	4216 KB	Output is correct
7	Correct	56 ms	4216 KB	Output is correct
8	Correct	53 ms	4216 KB	Output is correct
9	Correct	62 ms	4216 KB	Output is correct
10	Correct	54 ms	4216 KB	Output is correct
11	Correct	60 ms	4140 KB	Output is correct
12	Correct	53 ms	4216 KB	Output is correct
13	Correct	54 ms	4216 KB	Output is correct
14	Correct	51 ms	4216 KB	Output is correct
15	Correct	58 ms	4216 KB	Output is correct
16	Correct	55 ms	4216 KB	Output is correct
17	Correct	55 ms	4216 KB	Output is correct
18	Correct	485 ms	32428 KB	Output is correct
19	Correct	485 ms	32556 KB	Output is correct
20	Correct	544 ms	32428 KB	Output is correct
21	Correct	60 ms	4344 KB	Output is correct
22	Correct	53 ms	4216 KB	Output is correct
23	Correct	155 ms	6136 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	55 ms	4216 KB	Output is correct
3	Correct	60 ms	4216 KB	Output is correct
4	Correct	570 ms	32484 KB	Output is correct
5	Correct	55 ms	4216 KB	Output is correct
6	Correct	59 ms	4132 KB	Output is correct
7	Correct	56 ms	4216 KB	Output is correct
8	Correct	56 ms	4216 KB	Output is correct
9	Correct	54 ms	4216 KB	Output is correct
10	Correct	56 ms	4216 KB	Output is correct
11	Correct	56 ms	4216 KB	Output is correct
12	Correct	51 ms	4216 KB	Output is correct
13	Correct	56 ms	4216 KB	Output is correct
14	Correct	524 ms	32428 KB	Output is correct
15	Correct	55 ms	3964 KB	Output is correct
16	Correct	488 ms	32556 KB	Output is correct
17	Correct	491 ms	32556 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	10 ms	1016 KB	Output is correct
3	Correct	12 ms	1152 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	4 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	4 ms	384 KB	Output is correct
15	Correct	4 ms	384 KB	Output is correct
16	Correct	9 ms	1024 KB	Output is correct
17	Correct	57 ms	3960 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Incorrect	5 ms	384 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #212662

Compilation message