oj.uz

Submission #641079

# Submission time Handle Problem Language Result Execution time Memory
641079 2022-09-16T00:37:31 Z ymm Strange Device (APIO19_strange_device) C++17
15 / 100
 1284 ms 332 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

set<pll> s;

void add(ll l, ll r)
{
	auto it = s.lower_bound(pll{l, -1});
	if (it != s.begin()) {
		--it;
		if (it->second >= l) {
			l = it->first;
			s.erase(it++);
		} else {
			++it;
		}
	}
	while (it != s.end() && r >= it->first) {
		r = max(r, it->second);
		s.erase(it++);
	}
	s.insert({l, r});
}

int main()
{
	ll n, A, B;
	cin >> n >> A >> B;
	__int128 p = (__int128)A * B / __gcd(A, B+1);
	if (p < LONG_LONG_MAX)
		p = p * B / __gcd((ll)p, B);
	Loop (i,0,n) {
		ll l, r;
		cin >> l >> r;
		if (r - l + 1 >= p) {
			l = 0;
			r = p;
		} else {
			l %= p;
			r %= p;
			++r;
		}
		if (l < r) {
			add(l, r);
		} else {
			add(l, p);
			add(0, r);
		}
	}
	ll ans = 0;
	for (auto [x, y] : s)
		ans += y - x;
	cout << ans << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 13 ms 316 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 212 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 1262 ms 300 KB Output is correct
3 Correct 1243 ms 296 KB Output is correct
4 Correct 1244 ms 296 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 1262 ms 300 KB Output is correct
3 Correct 1243 ms 296 KB Output is correct
4 Correct 1244 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1271 ms 308 KB Output is correct
7 Correct 1251 ms 304 KB Output is correct
8 Correct 1270 ms 296 KB Output is correct
9 Correct 1272 ms 288 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 1262 ms 300 KB Output is correct
3 Correct 1243 ms 296 KB Output is correct
4 Correct 1244 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 126 ms 212 KB Output is correct
7 Correct 127 ms 300 KB Output is correct
8 Correct 128 ms 288 KB Output is correct
9 Correct 125 ms 288 KB Output is correct
10 Correct 128 ms 304 KB Output is correct
11 Correct 134 ms 304 KB Output is correct
12 Correct 127 ms 212 KB Output is correct
13 Correct 126 ms 284 KB Output is correct
14 Correct 127 ms 212 KB Output is correct
15 Correct 139 ms 292 KB Output is correct
16 Incorrect 130 ms 212 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 127 ms 300 KB Output is correct
3 Correct 127 ms 296 KB Output is correct
4 Correct 1275 ms 332 KB Output is correct
5 Correct 127 ms 212 KB Output is correct
6 Correct 130 ms 292 KB Output is correct
7 Correct 127 ms 292 KB Output is correct
8 Correct 139 ms 300 KB Output is correct
9 Correct 130 ms 292 KB Output is correct
10 Correct 128 ms 212 KB Output is correct
11 Correct 130 ms 296 KB Output is correct
12 Correct 195 ms 284 KB Output is correct
13 Correct 131 ms 296 KB Output is correct
14 Correct 1284 ms 300 KB Output is correct
15 Incorrect 128 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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