oj.uz

Submission #977060

# Submission time Handle Problem Language Result Execution time Memory
977060 2024-05-07T10:55:24 Z dubabuba Strange Device (APIO19_strange_device) C++14
10 / 100
 1252 ms 63032 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

int gcd(int a, int b) {
	if(a == 0) return b;
	if(b == 0) return a;
	return gcd(b % a, a);
}

signed main() {
	int a, b, n;
	cin >> n >> a >> b;
	int t = a / gcd(a, b + 1) * b;
	// tree *root = new tree(0, t - 1);
	set<pii> v;

	int l, r; bool gay = false;
	for(int i = 0; i < n; i++) {
		cin >> l >> r;
		if(r - l + 1 >= t) {
			gay = 1;
			continue;
		}

		l %= t;
		r %= t;

		if(l <= r) {
			// root->upt(l, r);
			v.insert(MP(l, r));
		}
		else {
			// root->upt(l, t - 1);
			// root->upt(0, r);
			v.insert(MP(l, t - 1));
			v.insert(MP(0, r));
		}
	}

	if(gay) {
		cout << t << endl;
		return 0;
	}

	int ans = 0;
	l = 0, r = 0;
	for(pii p : v) {
		// cout << p.ff << ' ' << p.ss << endl;
		if(r < p.ff) {
			// cout << " + " << r - l + 1 << endl;
			ans += (r - l + 1);
			l = p.ff;
		}
		r = max(r, p.ss);
	}

	ans += (r - l + 1);
	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 11 ms 856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 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 2 ms 348 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 697 ms 408 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 1120 ms 62968 KB Output is correct
3 Correct 1192 ms 63032 KB Output is correct
4 Correct 1152 ms 62804 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1120 ms 62968 KB Output is correct
3 Correct 1192 ms 63032 KB Output is correct
4 Correct 1152 ms 62804 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1200 ms 62904 KB Output is correct
7 Correct 1215 ms 62804 KB Output is correct
8 Correct 1141 ms 62912 KB Output is correct
9 Incorrect 1252 ms 62976 KB Output isn't correct
10 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 1120 ms 62968 KB Output is correct
3 Correct 1192 ms 63032 KB Output is correct
4 Correct 1152 ms 62804 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 110 ms 6456 KB Output is correct
7 Correct 108 ms 6608 KB Output is correct
8 Correct 110 ms 6428 KB Output is correct
9 Correct 111 ms 6476 KB Output is correct
10 Correct 111 ms 6480 KB Output is correct
11 Correct 119 ms 6476 KB Output is correct
12 Correct 112 ms 6532 KB Output is correct
13 Incorrect 124 ms 6668 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 144 ms 6504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 11 ms 856 KB Output isn't correct
3 Halted 0 ms 0 KB -