Submission #1035190

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1035190	2024-07-26T06:11:38 Z	Halym2007	Strange Device (APIO19_strange_device)	C++17	35 / 100	321 ms	69728 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define sz size()
#define pii pair <ll, ll>
const int N = 1e7 + 5;
#define ll long long
#define pb push_back
vector <pii> v;
ll n, a, b, l[N], r[N];
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> a >> b;
	__int128 m = a / __gcd (a, b + 1) * b;
	for (int i = 1; i <= n; ++i) {
		cin >> l[i] >> r[i];
	}
	if (r[n] < m) {
		ll jog = 0;
		for (int i = 1; i <= n; ++i) {
			jog += r[i] - l[i] + 1;
		}
		cout << jog;
		return 0;
	}
	for (int i = 1; i <= n; ++i) {
		if (r[i] - l[i] + 1 >= m) {
			return cout << (ll)m, 0;
		}
		if (l[i] % m > r[i] % m) {
			v.pb ({l[i] % m, m - 1});
			v.pb ({0, r[i] % m});
		}
		else {
			v.pb ({l[i] % m, r[i] % m});
		}
	}
	sort (v.begin(), v.end());
//	for (auto i : v) {
//		cout << i.ff << " " << i.ss << "\n";
//	}
//	return 0;
	ll l1 = v[0].ff, r1 = v[0].ss, jogap = 0;
	for (int i = 1; i < (int)v.sz; ++i) {
		if (v[i].ff <= r1) r1 = max (r1, v[i].ss);
		
		else {
			jogap += r1 - l1 + 1;
			l1 = v[i].ff; 
			r1 = v[i].ss;
		}
	}
	jogap += r1 - l1 + 1;
	cout << jogap;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	5 ms	1372 KB	Output is correct
3	Correct	3 ms	1244 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	1372 KB	Output is correct
17	Correct	31 ms	7768 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Incorrect	348 KB	Output isn't correct
6	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	208 ms	55108 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	286 ms	65376 KB	Output is correct
3	Correct	284 ms	65220 KB	Output is correct
4	Correct	280 ms	65400 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	286 ms	65376 KB	Output is correct
3	Correct	284 ms	65220 KB	Output is correct
4	Correct	280 ms	65400 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	287 ms	65232 KB	Output is correct
7	Correct	268 ms	65444 KB	Output is correct
8	Correct	269 ms	65220 KB	Output is correct
9	Correct	288 ms	65204 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	286 ms	65376 KB	Output is correct
3	Correct	284 ms	65220 KB	Output is correct
4	Correct	280 ms	65400 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	26 ms	7728 KB	Output is correct
7	Correct	28 ms	7640 KB	Output is correct
8	Correct	35 ms	7676 KB	Output is correct
9	Correct	29 ms	7564 KB	Output is correct
10	Correct	27 ms	7640 KB	Output is correct
11	Correct	32 ms	7780 KB	Output is correct
12	Correct	27 ms	7828 KB	Output is correct
13	Correct	29 ms	7632 KB	Output is correct
14	Correct	26 ms	8144 KB	Output is correct
15	Correct	30 ms	7892 KB	Output is correct
16	Correct	29 ms	7852 KB	Output is correct
17	Correct	27 ms	7888 KB	Output is correct
18	Correct	278 ms	69628 KB	Output is correct
19	Correct	268 ms	69720 KB	Output is correct
20	Correct	289 ms	69700 KB	Output is correct
21	Correct	30 ms	7812 KB	Output is correct
22	Correct	26 ms	7888 KB	Output is correct
23	Correct	89 ms	26676 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	29 ms	7548 KB	Output is correct
3	Correct	29 ms	7888 KB	Output is correct
4	Correct	297 ms	69644 KB	Output is correct
5	Correct	29 ms	7900 KB	Output is correct
6	Correct	30 ms	7892 KB	Output is correct
7	Correct	30 ms	7884 KB	Output is correct
8	Correct	29 ms	7932 KB	Output is correct
9	Correct	28 ms	7884 KB	Output is correct
10	Correct	29 ms	7896 KB	Output is correct
11	Correct	29 ms	7772 KB	Output is correct
12	Correct	25 ms	7896 KB	Output is correct
13	Correct	29 ms	7888 KB	Output is correct
14	Correct	321 ms	69728 KB	Output is correct
15	Correct	29 ms	7868 KB	Output is correct
16	Correct	318 ms	69640 KB	Output is correct
17	Correct	275 ms	69684 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	5 ms	1372 KB	Output is correct
3	Correct	3 ms	1244 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	1372 KB	Output is correct
17	Correct	31 ms	7768 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1035190

Compilation message