oj.uz

Submission #1044619

# Submission time Handle Problem Language Result Execution time Memory
1044619 2024-08-05T11:44:47 Z Onur_Ilgaz Strange Device (APIO19_strange_device) C++17
10 / 100
 407 ms 524456 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int C = inf * 2;

struct segtree {
	int n;
	struct node {
		int sum, l, r;
		bool set;
		node(): sum(0), l(0), r(0), set(false) {}
	};
	vector <node> t;
	int newnode() {
		t.push_back(node());
		return t.size() - 1;
	}
	void init(int size) {
		n = size;
		newnode();
	}
	void set(int l, int r) {
		return update(0, 0, n - 1, l, r);
	}
	void update(int v, int l, int r, int ul, int ur) {
		if(l >= ul and r <= ur) {
			t[v].sum = (r - l + 1);
			t[v].set = 1;
			return;
		}
		if(t[v].set) return;
		if(!t[v].l) {
			t[v].l = newnode();
			t[v].r = newnode();
		}
		int 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
	int n, a, b;
	cin >> n >> a >> b;
	int tekrar = gcd(a, b + 1);
	if(tekrar > C / a / b) {
		int sum = 0;
		for(int i = 0; i < n; i++) {
			int l, r;
			cin >> l >> r;
			sum += r - l + 1;
		}
		cout << sum << "\n";
		return 0;
	}
	tekrar = tekrar * a * b;
	t.init(tekrar);
	for(int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		if(r - l + 1 >= tekrar) {
			cout << tekrar << "\n";
			return 0;
		}
		int 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 6 ms 4816 KB Output is correct
3 Correct 7 ms 6352 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

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 1500 KB Output is correct
3 Correct 2 ms 1500 KB Output is correct
4 Correct 1 ms 1500 KB Output is correct
5 Correct 407 ms 436 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 387 ms 66616 KB Output is correct
3 Runtime error 351 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 1 ms 348 KB Output is correct
2 Correct 387 ms 66616 KB Output is correct
3 Runtime error 351 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 1 ms 348 KB Output is correct
2 Correct 387 ms 66616 KB Output is correct
3 Runtime error 351 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 0 ms 344 KB Output is correct
2 Correct 88 ms 66488 KB Output is correct
3 Correct 123 ms 132112 KB Output is correct
4 Runtime error 376 ms 524456 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 4816 KB Output is correct
3 Correct 7 ms 6352 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -