oj.uz

Submission #732039

# Submission time Handle Problem Language Result Execution time Memory
732039 2023-04-28T09:39:51 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
35 / 100
 1539 ms 49404 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, A, B;
vector<pair<ll, ll>> segs;
void solve2() {
	assert(0);
	ll ans = 0;
	for(auto & [l, r] : segs) {
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
}

ll gcd(ll a, ll b) {
	if(a > b) swap(a, b);
	if(a == 1 || b == 1) return 1;
	if(a == 0) return b;
	if(b == 0) return a;
	return gcd(a, b % a);
}

main() {
	cin >> n >> A >> B;
	segs.resize(n);
	ll cycle = 1e18;
	ll C = A / (gcd(B + 1, A));
	if((B * C) / C == B) cycle = B * C;
	else {
		solve2();
		return 0;
	}
	vector<pair<ll, bool>> evt;
	for(auto & [l, r] : segs) {
		cin >> l >> r;
		r++;
		if(l >= cycle) {
			ll tmp = (l / cycle) * cycle;
			l -= tmp;
			r -= tmp;
		}
		if(r >= cycle*2) {
			cout << cycle << endl;
			return 0;
		}
		if(r >= cycle) {
			evt.push_back({l, true});
			evt.push_back({0, true});
			evt.push_back({r - cycle, false});
		} else {
			evt.push_back({l, true});
			evt.push_back({r, false});
		}
	}
	sort(evt.begin(), evt.end());
	ll prev = 0;
	int cnt = 0;
	ll ans = 0;
	for(auto [t, b] : evt) {
		ll delta = t - prev;
		prev = t;
		if(cnt > 0) ans += delta;
		if(b) cnt++;
		else cnt--;
	}
	if(cnt > 0) ans += cycle - prev;
	cout << ans << endl;
}

Compilation message

strange_device.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 14 ms 1200 KB Output is correct
3 Correct 16 ms 1164 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 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 14 ms 1460 KB Output is correct
17 Correct 145 ms 6452 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 312 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 983 ms 48872 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1362 ms 48936 KB Output is correct
3 Correct 1438 ms 48984 KB Output is correct
4 Correct 1458 ms 49140 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1362 ms 48936 KB Output is correct
3 Correct 1438 ms 48984 KB Output is correct
4 Correct 1458 ms 49140 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1412 ms 48896 KB Output is correct
7 Correct 1400 ms 48952 KB Output is correct
8 Correct 1396 ms 49056 KB Output is correct
9 Correct 1489 ms 49028 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1362 ms 48936 KB Output is correct
3 Correct 1438 ms 48984 KB Output is correct
4 Correct 1458 ms 49140 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 138 ms 6360 KB Output is correct
7 Correct 149 ms 6404 KB Output is correct
8 Correct 142 ms 6368 KB Output is correct
9 Correct 145 ms 6396 KB Output is correct
10 Correct 136 ms 6384 KB Output is correct
11 Correct 147 ms 6444 KB Output is correct
12 Correct 139 ms 6420 KB Output is correct
13 Correct 147 ms 6392 KB Output is correct
14 Correct 139 ms 6428 KB Output is correct
15 Correct 167 ms 6400 KB Output is correct
16 Correct 178 ms 6444 KB Output is correct
17 Correct 135 ms 6408 KB Output is correct
18 Correct 1450 ms 48980 KB Output is correct
19 Correct 1387 ms 48892 KB Output is correct
20 Correct 1539 ms 48896 KB Output is correct
21 Correct 209 ms 6460 KB Output is correct
22 Correct 130 ms 6396 KB Output is correct
23 Correct 456 ms 22548 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 150 ms 6212 KB Output is correct
3 Correct 150 ms 6160 KB Output is correct
4 Correct 1523 ms 48992 KB Output is correct
5 Correct 143 ms 6208 KB Output is correct
6 Correct 141 ms 6220 KB Output is correct
7 Correct 145 ms 6140 KB Output is correct
8 Correct 146 ms 6204 KB Output is correct
9 Correct 140 ms 6200 KB Output is correct
10 Correct 147 ms 6252 KB Output is correct
11 Correct 151 ms 6112 KB Output is correct
12 Correct 133 ms 6188 KB Output is correct
13 Correct 142 ms 6220 KB Output is correct
14 Correct 1476 ms 49108 KB Output is correct
15 Correct 145 ms 6220 KB Output is correct
16 Correct 1362 ms 49404 KB Output is correct
17 Correct 1364 ms 49312 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 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 Correct 14 ms 1200 KB Output is correct
3 Correct 16 ms 1164 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 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 14 ms 1460 KB Output is correct
17 Correct 145 ms 6452 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -