Submission #410636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410636	2021-05-23T08:07:59 Z	dynam1c	Strange Device (APIO19_strange_device)	C++17	65 / 100	955 ms	100304 KB

strange_device

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

#define lo __int128

lo _gcd(lo x, lo y) {
	if (x == 0) return y;
	return _gcd(y % x, x);
}

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	ll n, a, b;
	cin >> n >> a >> b;
	lo g = _gcd(b+1, (lo) a*b);
	lo m = (lo) a * b / g;
	vector<pair<lo, int>> evs;
	for (int i = 0; i < n; i++) {
		ll xl, xr;
		cin >> xl >> xr;
		xr++;
		lo l = xl % m;
		lo r = xr % m;
		if (r <= l)
			evs.emplace_back(0, -1), evs.emplace_back(r, 1), evs.emplace_back(l, -1), evs.emplace_back(m, 1);
		else
			evs.emplace_back(l, -1), evs.emplace_back(r, 1);
	}
	sort(all(evs));
	ll res = 0;
	lo p = 0;
	int c = 0;
	for (auto [x, t] : evs) {
		if (c == 0) p = x;
		c -= t;
		if (c == 0) res += x-p;
	}
	cout << res << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	7 ms	1484 KB	Output is correct
3	Correct	7 ms	1484 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	7 ms	1484 KB	Output is correct
17	Correct	80 ms	8536 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 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	204 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	500 ms	73284 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	685 ms	66008 KB	Output is correct
3	Correct	760 ms	82608 KB	Output is correct
4	Correct	717 ms	82604 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	685 ms	66008 KB	Output is correct
3	Correct	760 ms	82608 KB	Output is correct
4	Correct	717 ms	82604 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	732 ms	82572 KB	Output is correct
7	Correct	698 ms	100304 KB	Output is correct
8	Correct	697 ms	100116 KB	Output is correct
9	Correct	886 ms	100192 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	685 ms	66008 KB	Output is correct
3	Correct	760 ms	82608 KB	Output is correct
4	Correct	717 ms	82604 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	65 ms	11248 KB	Output is correct
7	Correct	70 ms	11316 KB	Output is correct
8	Correct	61 ms	11232 KB	Output is correct
9	Correct	67 ms	11320 KB	Output is correct
10	Correct	62 ms	11320 KB	Output is correct
11	Correct	76 ms	11316 KB	Output is correct
12	Correct	63 ms	11312 KB	Output is correct
13	Correct	77 ms	11304 KB	Output is correct
14	Correct	61 ms	11232 KB	Output is correct
15	Correct	83 ms	11284 KB	Output is correct
16	Correct	75 ms	11316 KB	Output is correct
17	Correct	64 ms	11316 KB	Output is correct
18	Correct	701 ms	82528 KB	Output is correct
19	Correct	678 ms	67564 KB	Output is correct
20	Correct	934 ms	67540 KB	Output is correct
21	Correct	92 ms	11316 KB	Output is correct
22	Correct	60 ms	11316 KB	Output is correct
23	Correct	195 ms	43008 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	77 ms	11316 KB	Output is correct
3	Correct	82 ms	11228 KB	Output is correct
4	Correct	955 ms	66608 KB	Output is correct
5	Correct	76 ms	11320 KB	Output is correct
6	Correct	75 ms	11316 KB	Output is correct
7	Correct	76 ms	11316 KB	Output is correct
8	Correct	81 ms	11264 KB	Output is correct
9	Correct	72 ms	11248 KB	Output is correct
10	Correct	88 ms	11244 KB	Output is correct
11	Correct	83 ms	11240 KB	Output is correct
12	Correct	77 ms	11312 KB	Output is correct
13	Correct	81 ms	11308 KB	Output is correct
14	Correct	896 ms	66652 KB	Output is correct
15	Correct	83 ms	11228 KB	Output is correct
16	Correct	662 ms	67496 KB	Output is correct
17	Correct	695 ms	67564 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #8
0 / 30.0

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

Submission #410636

Compilation message