Submission #212661

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
212661	2020-03-24T03:21:09 Z	vioalbert	Strange Device (APIO19_strange_device)	C++14	65 / 100	594 ms	69812 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;

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	9 ms	640 KB	Output is correct
3	Correct	10 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 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	4 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	10 ms	640 KB	Output is correct
17	Correct	60 ms	3576 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	388 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	369 ms	41276 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	490 ms	32428 KB	Output is correct
3	Correct	515 ms	69812 KB	Output is correct
4	Correct	485 ms	69676 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	490 ms	32428 KB	Output is correct
3	Correct	515 ms	69812 KB	Output is correct
4	Correct	485 ms	69676 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	487 ms	69548 KB	Output is correct
7	Correct	524 ms	69804 KB	Output is correct
8	Correct	519 ms	69548 KB	Output is correct
9	Correct	543 ms	69548 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	490 ms	32428 KB	Output is correct
3	Correct	515 ms	69812 KB	Output is correct
4	Correct	485 ms	69676 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	53 ms	7288 KB	Output is correct
7	Correct	56 ms	7288 KB	Output is correct
8	Correct	56 ms	7288 KB	Output is correct
9	Correct	66 ms	7288 KB	Output is correct
10	Correct	53 ms	7288 KB	Output is correct
11	Correct	56 ms	7288 KB	Output is correct
12	Correct	55 ms	7288 KB	Output is correct
13	Correct	61 ms	7548 KB	Output is correct
14	Correct	52 ms	7216 KB	Output is correct
15	Correct	58 ms	7288 KB	Output is correct
16	Correct	56 ms	7288 KB	Output is correct
17	Correct	56 ms	7288 KB	Output is correct
18	Correct	512 ms	69548 KB	Output is correct
19	Correct	505 ms	69548 KB	Output is correct
20	Correct	552 ms	69680 KB	Output is correct
21	Correct	58 ms	7288 KB	Output is correct
22	Correct	51 ms	7292 KB	Output is correct
23	Correct	162 ms	18296 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	58 ms	7288 KB	Output is correct
3	Correct	58 ms	7288 KB	Output is correct
4	Correct	594 ms	69548 KB	Output is correct
5	Correct	56 ms	7288 KB	Output is correct
6	Correct	57 ms	7288 KB	Output is correct
7	Correct	62 ms	7484 KB	Output is correct
8	Correct	58 ms	7288 KB	Output is correct
9	Correct	60 ms	7288 KB	Output is correct
10	Correct	57 ms	7288 KB	Output is correct
11	Correct	60 ms	7288 KB	Output is correct
12	Correct	54 ms	7288 KB	Output is correct
13	Correct	60 ms	7288 KB	Output is correct
14	Correct	568 ms	69552 KB	Output is correct
15	Correct	58 ms	7032 KB	Output is correct
16	Correct	538 ms	69676 KB	Output is correct
17	Correct	548 ms	69612 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	9 ms	640 KB	Output is correct
3	Correct	10 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 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	4 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	10 ms	640 KB	Output is correct
17	Correct	60 ms	3576 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	388 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #212661

Compilation message