oj.uz

Submission #732042

# Submission time Handle Problem Language Result Execution time Memory
732042 2023-04-28T09:50:08 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
35 / 100
 1712 ms 48972 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, A, B;
vector<pair<ll, ll>> segs;
void solve2() {
	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);
}

//x(B+1) == 0
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;
	}
	if(cycle > 1e18 + 10) cycle = 1e18 + 10;
	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 0 ms 212 KB Output is correct
2 Correct 14 ms 1104 KB Output is correct
3 Correct 15 ms 1088 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 14 ms 1032 KB Output is correct
17 Correct 149 ms 6052 KB Output is correct
18 Incorrect 0 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 212 KB Output is correct
2 Correct 0 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 Incorrect 0 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 0 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 340 KB Output is correct
5 Correct 1006 ms 48940 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1368 ms 48944 KB Output is correct
3 Correct 1447 ms 48864 KB Output is correct
4 Correct 1364 ms 48844 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1368 ms 48944 KB Output is correct
3 Correct 1447 ms 48864 KB Output is correct
4 Correct 1364 ms 48844 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1456 ms 48956 KB Output is correct
7 Correct 1352 ms 48808 KB Output is correct
8 Correct 1360 ms 48840 KB Output is correct
9 Correct 1478 ms 48832 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1368 ms 48944 KB Output is correct
3 Correct 1447 ms 48864 KB Output is correct
4 Correct 1364 ms 48844 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 155 ms 6088 KB Output is correct
7 Correct 141 ms 6092 KB Output is correct
8 Correct 135 ms 6008 KB Output is correct
9 Correct 135 ms 6076 KB Output is correct
10 Correct 150 ms 6072 KB Output is correct
11 Correct 139 ms 6016 KB Output is correct
12 Correct 131 ms 6076 KB Output is correct
13 Correct 154 ms 6044 KB Output is correct
14 Correct 136 ms 6076 KB Output is correct
15 Correct 164 ms 6216 KB Output is correct
16 Correct 147 ms 6020 KB Output is correct
17 Correct 139 ms 6096 KB Output is correct
18 Correct 1428 ms 48888 KB Output is correct
19 Correct 1358 ms 48860 KB Output is correct
20 Correct 1477 ms 48952 KB Output is correct
21 Correct 146 ms 6008 KB Output is correct
22 Correct 132 ms 6028 KB Output is correct
23 Correct 437 ms 22176 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 148 ms 6088 KB Output is correct
3 Correct 141 ms 6012 KB Output is correct
4 Correct 1712 ms 48956 KB Output is correct
5 Correct 159 ms 6056 KB Output is correct
6 Correct 156 ms 5988 KB Output is correct
7 Correct 142 ms 6080 KB Output is correct
8 Correct 141 ms 6008 KB Output is correct
9 Correct 152 ms 6068 KB Output is correct
10 Correct 157 ms 6072 KB Output is correct
11 Correct 138 ms 6076 KB Output is correct
12 Correct 138 ms 5988 KB Output is correct
13 Correct 140 ms 6076 KB Output is correct
14 Correct 1485 ms 48864 KB Output is correct
15 Correct 140 ms 6076 KB Output is correct
16 Correct 1393 ms 48972 KB Output is correct
17 Correct 1366 ms 48840 KB Output is correct
18 Incorrect 0 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 0 ms 212 KB Output is correct
2 Correct 14 ms 1104 KB Output is correct
3 Correct 15 ms 1088 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 14 ms 1032 KB Output is correct
17 Correct 149 ms 6052 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -