Submission #367992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367992	2021-02-19T08:33:20 Z	grt	Strange Device (APIO19_strange_device)	C++17	35 / 100	762 ms	56936 KB

strange_device

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

int n;
ll a, b;
vector<pair<ll,int>>p;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> a >> b;
	ll g = __gcd(a, b + 1);
	a /= g;
	ll mod = a * b;
	for(int i = 1; i <= n; ++i) {
		ll l, r;
		cin >> l >> r;
		if(r - l + 1 >= mod) {
			p.PB({0,1});
			p.PB({mod,-1});
		} else {
			if(l % (mod) <= r % (mod)) {
				p.PB({l % (mod), 1});
				p.PB({(r % (mod)) + 1, -1});
			} else {
				p.PB({(l % (mod)), 1});
				p.PB({mod, -1});
				p.PB({0, 1});
				p.PB({r % (mod) + 1, -1});
			}
		}
	}
	sort(p.begin(), p.end());
	ll ans = 0;
	int cnt = 0;
	ll pr = 0;
	for(auto it : p) {
		if(cnt > 0) ans += it.ST - pr;
		cnt += it.ND;
		pr = it.ST;
	}
	cout << ans;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	6 ms	1540 KB	Output is correct
3	Correct	7 ms	1392 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	376 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	6 ms	1392 KB	Output is correct
17	Correct	67 ms	7268 KB	Output is correct
18	Incorrect	1 ms	364 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Incorrect	1 ms	384 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	431 ms	56936 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	598 ms	49868 KB	Output is correct
3	Correct	628 ms	49852 KB	Output is correct
4	Correct	575 ms	49852 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	598 ms	49868 KB	Output is correct
3	Correct	628 ms	49852 KB	Output is correct
4	Correct	575 ms	49852 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	599 ms	49852 KB	Output is correct
7	Correct	605 ms	49852 KB	Output is correct
8	Correct	584 ms	48792 KB	Output is correct
9	Correct	692 ms	49560 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	598 ms	49868 KB	Output is correct
3	Correct	628 ms	49852 KB	Output is correct
4	Correct	575 ms	49852 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	75 ms	7268 KB	Output is correct
7	Correct	61 ms	7396 KB	Output is correct
8	Correct	60 ms	7268 KB	Output is correct
9	Correct	58 ms	7268 KB	Output is correct
10	Correct	57 ms	7268 KB	Output is correct
11	Correct	60 ms	7268 KB	Output is correct
12	Correct	68 ms	7392 KB	Output is correct
13	Correct	63 ms	7268 KB	Output is correct
14	Correct	58 ms	7268 KB	Output is correct
15	Correct	67 ms	7268 KB	Output is correct
16	Correct	68 ms	7268 KB	Output is correct
17	Correct	68 ms	7268 KB	Output is correct
18	Correct	614 ms	50268 KB	Output is correct
19	Correct	579 ms	49304 KB	Output is correct
20	Correct	724 ms	49968 KB	Output is correct
21	Correct	66 ms	7288 KB	Output is correct
22	Correct	55 ms	7396 KB	Output is correct
23	Correct	171 ms	26880 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	63 ms	7268 KB	Output is correct
3	Correct	64 ms	7268 KB	Output is correct
4	Correct	762 ms	49988 KB	Output is correct
5	Correct	63 ms	7268 KB	Output is correct
6	Correct	64 ms	7268 KB	Output is correct
7	Correct	63 ms	7268 KB	Output is correct
8	Correct	66 ms	7268 KB	Output is correct
9	Correct	63 ms	7264 KB	Output is correct
10	Correct	68 ms	7416 KB	Output is correct
11	Correct	63 ms	7268 KB	Output is correct
12	Correct	58 ms	7388 KB	Output is correct
13	Correct	69 ms	7460 KB	Output is correct
14	Correct	712 ms	42676 KB	Output is correct
15	Correct	69 ms	7392 KB	Output is correct
16	Correct	570 ms	42576 KB	Output is correct
17	Correct	591 ms	42540 KB	Output is correct
18	Incorrect	1 ms	364 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	6 ms	1540 KB	Output is correct
3	Correct	7 ms	1392 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	376 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	6 ms	1392 KB	Output is correct
17	Correct	67 ms	7268 KB	Output is correct
18	Incorrect	1 ms	364 KB	Output isn't correct

Submission #367992

Compilation message