oj.uz

Submission #641082

# Submission time Handle Problem Language Result Execution time Memory
641082 2022-09-16T00:49:43 Z ymm Strange Device (APIO19_strange_device) C++17
15 / 100
 1361 ms 604 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;
			auto tmp = it;
			++it;
			s.erase(tmp);
		} else {
			++it;
		}
	}
	while (it != s.end() && r >= it->first) {
		r = max(r, it->second);
		auto tmp = it;
		++it;
		s.erase(tmp);
	}
	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 396 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 224 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 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 1 ms 212 KB Output is correct
2 Incorrect 2 ms 216 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 1 ms 216 KB Output is correct
2 Correct 1255 ms 308 KB Output is correct
3 Correct 1250 ms 484 KB Output is correct
4 Correct 1245 ms 480 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1255 ms 308 KB Output is correct
3 Correct 1250 ms 484 KB Output is correct
4 Correct 1245 ms 480 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1253 ms 500 KB Output is correct
7 Correct 1260 ms 500 KB Output is correct
8 Correct 1240 ms 500 KB Output is correct
9 Correct 1361 ms 468 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1255 ms 308 KB Output is correct
3 Correct 1250 ms 484 KB Output is correct
4 Correct 1245 ms 480 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 128 ms 376 KB Output is correct
7 Correct 127 ms 372 KB Output is correct
8 Correct 143 ms 468 KB Output is correct
9 Correct 130 ms 360 KB Output is correct
10 Correct 125 ms 372 KB Output is correct
11 Correct 126 ms 384 KB Output is correct
12 Correct 130 ms 340 KB Output is correct
13 Correct 125 ms 340 KB Output is correct
14 Correct 125 ms 340 KB Output is correct
15 Correct 144 ms 372 KB Output is correct
16 Incorrect 131 ms 372 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 128 ms 376 KB Output is correct
3 Correct 126 ms 380 KB Output is correct
4 Correct 1284 ms 604 KB Output is correct
5 Correct 126 ms 340 KB Output is correct
6 Correct 126 ms 340 KB Output is correct
7 Correct 129 ms 340 KB Output is correct
8 Correct 129 ms 340 KB Output is correct
9 Correct 130 ms 340 KB Output is correct
10 Correct 129 ms 384 KB Output is correct
11 Correct 132 ms 340 KB Output is correct
12 Correct 134 ms 364 KB Output is correct
13 Correct 126 ms 340 KB Output is correct
14 Correct 1302 ms 500 KB Output is correct
15 Incorrect 133 ms 384 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 396 KB Output isn't correct
3 Halted 0 ms 0 KB -