Submission #1044696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1044696	2024-08-05T12:32:26 Z	Onur_Ilgaz	Strange Device (APIO19_strange_device)	C++17	20 / 100	524 ms	524292 KB

strange_device

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define inf ((long long)1e18)
using namespace std;
const long long C = inf * 2;

struct segtree {
	long long n;
	struct node {
		long long sum;
		int l, r;
		node(): sum(0), l(0), r(0) {}
	};
	vector <node> t;
	int newnode() {
		t.push_back(node());
		return t.size() - 1;
	}
	void init(long long size) {
		n = size;
		newnode();
	}
	void set(long l, long r) {
		return update(0, 0, n - 1, l, r);
	}
	void update(int v, long long l, long long r, long long ul, long long ur) {
		if(l >= ul and r <= ur) {
			t[v].sum = (r - l + 1);
			return;
		}
		if(t[v].sum == r - l + 1) return;
		if(!t[v].l) {
			t[v].l = newnode();
			t[v].r = newnode();
		}
		long long m = (l + r) / 2;
		if(ul <= m) update(t[v].l, l, m, ul, ur);
		if(ur > m) update(t[v].r, m + 1, r, ul, ur);
		t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
	}
}t;

int32_t main(){
	fast
	long long n, a, b;
	cin >> n >> a >> b;
	__int128__ g = gcd(a, b + 1);
	__int128__ temp = (__int128__)a / g * b;
	if(temp > C) {
		long long sum = 0;
		for(int i = 0; i < n; i++) {
			long long l, r;
			cin >> l >> r;
			sum += r - l + 1;
		}
		cout << sum;
		return 0;
	}
	long long tekrar = temp;
	t.init(tekrar);
	for(int i = 0; i < n; i++) {
		long long l, r;
		cin >> l >> r;
		if(r - l + 1 >= tekrar) {
			cout << tekrar;
			return 0;
		}
		long long ll = l % tekrar, rr = r % tekrar;
		if(ll <= rr) {
			t.set(ll, rr);
		}
		else {
			t.set(0, rr);
			t.set(ll, tekrar - 1);
		}
	}
	cout << t.t[0].sum;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	6 ms	2776 KB	Output is correct
3	Correct	5 ms	2776 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	348 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	5 ms	2776 KB	Output is correct
17	Correct	35 ms	6108 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	604 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	1 ms	992 KB	Output is correct
3	Correct	1 ms	992 KB	Output is correct
4	Correct	1 ms	992 KB	Output is correct
5	Correct	366 ms	13032 KB	Output is correct

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	332 ms	48732 KB	Output is correct
3	Runtime error	524 ms	524292 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	332 ms	48732 KB	Output is correct
3	Runtime error	524 ms	524292 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	332 ms	48732 KB	Output is correct
3	Runtime error	524 ms	524292 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	57 ms	35956 KB	Output is correct
3	Correct	109 ms	68004 KB	Output is correct
4	Runtime error	472 ms	524288 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	6 ms	2776 KB	Output is correct
3	Correct	5 ms	2776 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	348 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	5 ms	2776 KB	Output is correct
17	Correct	35 ms	6108 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	600 KB	Output is correct
25	Correct	1 ms	992 KB	Output is correct
26	Correct	1 ms	992 KB	Output is correct
27	Correct	1 ms	992 KB	Output is correct
28	Correct	366 ms	13032 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	332 ms	48732 KB	Output is correct
31	Runtime error	524 ms	524292 KB	Execution killed with signal 9
32	Halted	0 ms	0 KB	-

Submission #1044696

Compilation message