Submission #1035193

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1035193	2024-07-26T06:15:12 Z	Halym2007	Strange Device (APIO19_strange_device)	C++17	35 / 100	341 ms	67876 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;
			v.pb ({0, m - 1});
			continue;
		}
		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 if (v[i].ff > r1) {
			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	1 ms	344 KB	Output is correct
2	Correct	3 ms	1372 KB	Output is correct
3	Correct	3 ms	1372 KB	Output is correct
4	Correct	0 ms	348 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	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	5 ms	1372 KB	Output is correct
17	Correct	33 ms	7880 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	600 KB	Output is correct
2	Correct	600 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	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	212 ms	56692 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	309 ms	67756 KB	Output is correct
3	Correct	293 ms	67780 KB	Output is correct
4	Correct	284 ms	67876 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	309 ms	67756 KB	Output is correct
3	Correct	293 ms	67780 KB	Output is correct
4	Correct	284 ms	67876 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	329 ms	67820 KB	Output is correct
7	Correct	272 ms	67868 KB	Output is correct
8	Correct	310 ms	67780 KB	Output is correct
9	Correct	341 ms	67832 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	309 ms	67756 KB	Output is correct
3	Correct	293 ms	67780 KB	Output is correct
4	Correct	284 ms	67876 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	29 ms	7848 KB	Output is correct
7	Correct	35 ms	7808 KB	Output is correct
8	Correct	27 ms	7848 KB	Output is correct
9	Correct	28 ms	7780 KB	Output is correct
10	Correct	30 ms	7884 KB	Output is correct
11	Correct	36 ms	7812 KB	Output is correct
12	Correct	27 ms	7884 KB	Output is correct
13	Correct	30 ms	7884 KB	Output is correct
14	Correct	29 ms	7888 KB	Output is correct
15	Correct	38 ms	7752 KB	Output is correct
16	Correct	52 ms	7760 KB	Output is correct
17	Correct	37 ms	7932 KB	Output is correct
18	Correct	298 ms	67528 KB	Output is correct
19	Correct	286 ms	67608 KB	Output is correct
20	Correct	321 ms	67524 KB	Output is correct
21	Correct	32 ms	7884 KB	Output is correct
22	Correct	27 ms	7888 KB	Output is correct
23	Correct	85 ms	26224 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	30 ms	7776 KB	Output is correct
3	Correct	30 ms	7896 KB	Output is correct
4	Correct	317 ms	67776 KB	Output is correct
5	Correct	30 ms	7888 KB	Output is correct
6	Correct	30 ms	7920 KB	Output is correct
7	Correct	30 ms	7888 KB	Output is correct
8	Correct	32 ms	7892 KB	Output is correct
9	Correct	30 ms	7884 KB	Output is correct
10	Correct	31 ms	7848 KB	Output is correct
11	Correct	31 ms	7768 KB	Output is correct
12	Correct	26 ms	7888 KB	Output is correct
13	Correct	30 ms	7884 KB	Output is correct
14	Correct	302 ms	67696 KB	Output is correct
15	Correct	30 ms	7888 KB	Output is correct
16	Correct	270 ms	67524 KB	Output is correct
17	Correct	274 ms	67636 KB	Output is correct
18	Incorrect	0 ms	344 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	3 ms	1372 KB	Output is correct
3	Correct	3 ms	1372 KB	Output is correct
4	Correct	0 ms	348 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	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	5 ms	1372 KB	Output is correct
17	Correct	33 ms	7880 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1035193

Compilation message