oj.uz

Submission #641078

# Submission time Handle Problem Language Result Execution time Memory
641078 2022-09-16T00:35:24 Z ymm Strange Device (APIO19_strange_device) C++17
10 / 100
 1378 ms 19960 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;
		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 1 ms 212 KB Output is correct
2 Incorrect 15 ms 684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 1373 ms 19960 KB Output is correct
3 Correct 1324 ms 11692 KB Output is correct
4 Correct 1325 ms 11688 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1373 ms 19960 KB Output is correct
3 Correct 1324 ms 11692 KB Output is correct
4 Correct 1325 ms 11688 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1326 ms 11628 KB Output is correct
7 Correct 1328 ms 11724 KB Output is correct
8 Correct 1336 ms 11636 KB Output is correct
9 Correct 1312 ms 11760 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1373 ms 19960 KB Output is correct
3 Correct 1324 ms 11692 KB Output is correct
4 Correct 1325 ms 11688 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 134 ms 4008 KB Output is correct
7 Correct 134 ms 4012 KB Output is correct
8 Correct 139 ms 3988 KB Output is correct
9 Correct 135 ms 3976 KB Output is correct
10 Correct 142 ms 3996 KB Output is correct
11 Correct 136 ms 4008 KB Output is correct
12 Correct 133 ms 3988 KB Output is correct
13 Correct 139 ms 3980 KB Output is correct
14 Correct 134 ms 4008 KB Output is correct
15 Correct 137 ms 3992 KB Output is correct
16 Incorrect 136 ms 4044 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 135 ms 3988 KB Output is correct
3 Correct 138 ms 3992 KB Output is correct
4 Correct 1363 ms 11660 KB Output is correct
5 Correct 138 ms 3920 KB Output is correct
6 Correct 135 ms 3988 KB Output is correct
7 Correct 140 ms 3984 KB Output is correct
8 Correct 136 ms 3884 KB Output is correct
9 Correct 135 ms 3988 KB Output is correct
10 Correct 143 ms 4000 KB Output is correct
11 Correct 141 ms 4004 KB Output is correct
12 Correct 134 ms 3996 KB Output is correct
13 Correct 134 ms 4004 KB Output is correct
14 Correct 1378 ms 11456 KB Output is correct
15 Incorrect 135 ms 4004 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 15 ms 684 KB Output isn't correct
3 Halted 0 ms 0 KB -