oj.uz

Submission #714921

# Submission time Handle Problem Language Result Execution time Memory
714921 2023-03-25T13:21:03 Z MISM06 Strange Device (APIO19_strange_device) C++14
20 / 100
 1780 ms 71512 KB 
//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

set < plll > s;

plll find (int id) {
	auto it = s.lower_bound({id + 1ll, {0, 0}});
	it = prev(it);
	return *it;
}

void add (ll l, ll r) {
	plll x = find(l);
	if (x.F < l) {
		s.erase(x);
		s.insert({x.F, {l - 1ll, x.S.S}});
		s.insert({l, x.S});
	}
	x = find(r);
	if (x.S.F > r) {
		s.erase(x);
		s.insert({x.F, {r, x.S.S}});
		s.insert({r + 1ll, x.S});
	}
	x = *s.lower_bound({l, {0, 0}});
	while (x.F <= r) {
		s.erase(x);
		if (x.S.F == r) break;
		x = *s.lower_bound({l, {0, 0}});
	}
	s.insert({l, {r, 1}});
}

void solve () {

	int n;
	ll A, B;
	cin >> n >> A >> B;
	dl a = A, b = (B + 1ll);
	dl x = __gcd(A, B + 1ll);
	dl lcm = (a * b) / x;
	dl y = lcm / b;
	dl bb = B;
	dl z = y * bb;
	ll t;
	if (z > 1e18) t = 1e8;
	else t = z;
	s.insert({0, {t - 1ll, 0}});
	s.insert({inf, {inf, inf}});
	s.insert({-1, {-1, -1}});
	bool ch = 0;
	ll en = t - 1ll;
	for (int i = 1; i <= n; i++) {
		ll l, r; cin >> l >> r;
		ll len = (r - l + 1ll);
		if (len >= t) {
			ch = 1;
			add(0, en);
		}
		if (ch) continue;
		l = l % t;
		r = r % t;
		if (l <= r) add(l, r);
		else {
			add(l, en);
			add(0, r);
		}
	}
	ll ans = 0;
	for (auto it = s.begin(); it != s.end(); ++it) {
		plll x = *it;
		if (x.S.S == 1) ans += (x.S.F - x.F + 1ll);
	}
	cout << ans << '\n';
}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	

	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//inhonorofsbi;

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 13 ms 1220 KB Output is correct
3 Correct 13 ms 1236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 13 ms 1236 KB Output is correct
17 Correct 128 ms 10276 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 343 ms 860 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 13 ms 1220 KB Output is correct
3 Correct 13 ms 1236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 13 ms 1236 KB Output is correct
17 Correct 128 ms 10276 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 320 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 328 KB Output is correct
28 Correct 343 ms 860 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1474 ms 63932 KB Output is correct
31 Incorrect 1780 ms 71512 KB Output isn't correct
32 Halted 0 ms 0 KB -