oj.uz

Submission #819968

# Submission time Handle Problem Language Result Execution time Memory
819968 2023-08-10T16:38:22 Z Alan Strange Device (APIO19_strange_device) C++17
15 / 100
 1548 ms 100212 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll inf = 1e18;

void add (set<pair<ll, ll>>& st, ll l, ll r) {
	auto it = st.lower_bound({l, 0}), tmp = it;
	if (it != st.begin() && (--tmp)->second >= l) {
		l = tmp->first;
		st.erase(tmp);
	}
	while (it != st.end()) {
		if (r >= it->first) {
			r = max(r, it->second);
			it = st.erase(it);
		} else break;
	}
	st.insert({l, r});
}

int main () {
	ll n, a, b;
	cin >> n >> a >> b;
	ll mod;
	if (a / gcd(a, b+1) > inf / b) mod = inf;
	else mod = a / gcd(a, b+1) * b;
	set<pair<ll, ll>> st;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		if (r-l+1 >= mod) {
			cout << mod << '\n';
			return 0;
		}
		if (l % mod > r % mod) {
			add(st, 0, r % mod);
			add(st, l % mod, mod-1);
		} else add(st, l % mod, r % mod);
	}
	ll ans = 0;
	for (auto& [l, r] : st) ans += r-l+1;
	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 12 ms 1196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1243 ms 99988 KB Output is correct
3 Correct 1204 ms 100028 KB Output is correct
4 Correct 1232 ms 100056 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1243 ms 99988 KB Output is correct
3 Correct 1204 ms 100028 KB Output is correct
4 Correct 1232 ms 100056 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1296 ms 100076 KB Output is correct
7 Correct 1239 ms 100132 KB Output is correct
8 Correct 1195 ms 100100 KB Output is correct
9 Correct 1358 ms 100132 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1243 ms 99988 KB Output is correct
3 Correct 1204 ms 100028 KB Output is correct
4 Correct 1232 ms 100056 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 115 ms 10180 KB Output is correct
7 Correct 111 ms 10212 KB Output is correct
8 Correct 111 ms 10176 KB Output is correct
9 Correct 117 ms 10184 KB Output is correct
10 Correct 114 ms 10120 KB Output is correct
11 Correct 120 ms 10240 KB Output is correct
12 Correct 114 ms 10156 KB Output is correct
13 Correct 140 ms 10180 KB Output is correct
14 Correct 122 ms 10260 KB Output is correct
15 Correct 123 ms 10188 KB Output is correct
16 Incorrect 137 ms 10240 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 118 ms 10156 KB Output is correct
3 Correct 120 ms 10232 KB Output is correct
4 Correct 1548 ms 100092 KB Output is correct
5 Correct 123 ms 10172 KB Output is correct
6 Correct 126 ms 10256 KB Output is correct
7 Correct 120 ms 10236 KB Output is correct
8 Correct 121 ms 10184 KB Output is correct
9 Correct 121 ms 10216 KB Output is correct
10 Correct 116 ms 10208 KB Output is correct
11 Correct 116 ms 10188 KB Output is correct
12 Correct 114 ms 10148 KB Output is correct
13 Correct 118 ms 10188 KB Output is correct
14 Correct 1363 ms 100212 KB Output is correct
15 Incorrect 121 ms 10172 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 12 ms 1196 KB Output isn't correct
3 Halted 0 ms 0 KB -