oj.uz

Submission #926648

# Submission time Handle Problem Language Result Execution time Memory
926648 2024-02-13T13:08:34 Z oblantis Strange Device (APIO19_strange_device) C++17
65 / 100
 442 ms 19376 KB 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
#define ih __int128
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 1e9+7;
const ll inf = 1e18 + 1;
const int maxn = 1e6 + 1;
set<pair<ih, ih>> s;
ll ans;
void upd(ll l, ll r){
	if(s.empty())return;
	vt<pair<ih, ih>> del;
	auto i = s.lower_bound({l, inf});
	if(i != s.begin())i--;
	if((*i).ss < l)i++;
	while(i != s.end() && (*i).ff <= r){
		if((*i).ff < l){
			s.insert({(*i).ff, l - 1});
			ans -= l - (*i).ff;
		}
		if((*i).ss > r){
			s.insert({r + 1, (*i).ss});
			ans -= (*i).ss - r;
		}
		del.pb(*i);
		ans += (*i).ss - (*i).ff + 1;
		i++;
	}
	for(auto i : del)s.erase(i);
}
void solve() {
	int n;
	ih a, b;
	ll A, B;
	cin >> n >> A >> B;
	a = A, b = B;
	ih md = a * b / __gcd(a, b + 1);
	s.insert({0, md - 1});
	for(int i = 0; i < n; i++){
		ll l, r;
		cin >> l >> r;
		l %= md, r %= md;
		if(l <= r)upd(l, r);
		else upd(0, r), upd(l, md - 1);
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 40 ms 2532 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.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 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 191 ms 13404 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 442 ms 19260 KB Output is correct
3 Correct 354 ms 18992 KB Output is correct
4 Correct 368 ms 19028 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 442 ms 19260 KB Output is correct
3 Correct 354 ms 18992 KB Output is correct
4 Correct 368 ms 19028 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 358 ms 19028 KB Output is correct
7 Correct 353 ms 19024 KB Output is correct
8 Correct 355 ms 19144 KB Output is correct
9 Correct 357 ms 19280 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 442 ms 19260 KB Output is correct
3 Correct 354 ms 18992 KB Output is correct
4 Correct 368 ms 19028 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 35 ms 2520 KB Output is correct
7 Correct 44 ms 2456 KB Output is correct
8 Correct 37 ms 2384 KB Output is correct
9 Correct 44 ms 2600 KB Output is correct
10 Correct 36 ms 2472 KB Output is correct
11 Correct 37 ms 2440 KB Output is correct
12 Correct 35 ms 2388 KB Output is correct
13 Correct 37 ms 2316 KB Output is correct
14 Correct 36 ms 2396 KB Output is correct
15 Correct 39 ms 2496 KB Output is correct
16 Correct 35 ms 2384 KB Output is correct
17 Correct 36 ms 2388 KB Output is correct
18 Correct 363 ms 19052 KB Output is correct
19 Correct 359 ms 19028 KB Output is correct
20 Correct 358 ms 19376 KB Output is correct
21 Correct 36 ms 2388 KB Output is correct
22 Correct 38 ms 2416 KB Output is correct
23 Correct 82 ms 7088 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 44 ms 2508 KB Output is correct
3 Correct 38 ms 2384 KB Output is correct
4 Correct 373 ms 18936 KB Output is correct
5 Correct 39 ms 2372 KB Output is correct
6 Correct 40 ms 2392 KB Output is correct
7 Correct 37 ms 2384 KB Output is correct
8 Correct 39 ms 2388 KB Output is correct
9 Correct 40 ms 2388 KB Output is correct
10 Correct 37 ms 2276 KB Output is correct
11 Correct 37 ms 2384 KB Output is correct
12 Correct 36 ms 2484 KB Output is correct
13 Correct 46 ms 2388 KB Output is correct
14 Correct 380 ms 18912 KB Output is correct
15 Correct 36 ms 2384 KB Output is correct
16 Correct 361 ms 19284 KB Output is correct
17 Correct 357 ms 19024 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 40 ms 2532 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -