oj.uz

Submission #732040

# Submission time Handle Problem Language Result Execution time Memory
732040 2023-04-28T09:41:04 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
35 / 100
 1554 ms 49176 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);
}

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:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | 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 1024 KB Output is correct
3 Correct 14 ms 1052 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 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 14 ms 1048 KB Output is correct
17 Correct 145 ms 6244 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 0 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 0 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 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 372 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1006 ms 48864 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1357 ms 48860 KB Output is correct
3 Correct 1384 ms 48880 KB Output is correct
4 Correct 1345 ms 48824 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 1357 ms 48860 KB Output is correct
3 Correct 1384 ms 48880 KB Output is correct
4 Correct 1345 ms 48824 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1377 ms 48908 KB Output is correct
7 Correct 1360 ms 48976 KB Output is correct
8 Correct 1356 ms 49148 KB Output is correct
9 Correct 1445 ms 48932 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1357 ms 48860 KB Output is correct
3 Correct 1384 ms 48880 KB Output is correct
4 Correct 1345 ms 48824 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 133 ms 6080 KB Output is correct
7 Correct 141 ms 6020 KB Output is correct
8 Correct 136 ms 6076 KB Output is correct
9 Correct 139 ms 6088 KB Output is correct
10 Correct 135 ms 5984 KB Output is correct
11 Correct 139 ms 6036 KB Output is correct
12 Correct 134 ms 5972 KB Output is correct
13 Correct 148 ms 6100 KB Output is correct
14 Correct 147 ms 6104 KB Output is correct
15 Correct 147 ms 6064 KB Output is correct
16 Correct 145 ms 6044 KB Output is correct
17 Correct 136 ms 6064 KB Output is correct
18 Correct 1362 ms 48920 KB Output is correct
19 Correct 1382 ms 48900 KB Output is correct
20 Correct 1554 ms 48912 KB Output is correct
21 Correct 143 ms 5996 KB Output is correct
22 Correct 132 ms 6000 KB Output is correct
23 Correct 436 ms 22160 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 143 ms 5976 KB Output is correct
3 Correct 138 ms 5976 KB Output is correct
4 Correct 1468 ms 48892 KB Output is correct
5 Correct 140 ms 6052 KB Output is correct
6 Correct 141 ms 6176 KB Output is correct
7 Correct 141 ms 6048 KB Output is correct
8 Correct 144 ms 5988 KB Output is correct
9 Correct 141 ms 6052 KB Output is correct
10 Correct 143 ms 6068 KB Output is correct
11 Correct 138 ms 6020 KB Output is correct
12 Correct 136 ms 6092 KB Output is correct
13 Correct 140 ms 6060 KB Output is correct
14 Correct 1441 ms 48932 KB Output is correct
15 Correct 146 ms 6040 KB Output is correct
16 Correct 1337 ms 49176 KB Output is correct
17 Correct 1374 ms 49072 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 1 ms 212 KB Output is correct
2 Correct 14 ms 1024 KB Output is correct
3 Correct 14 ms 1052 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 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 14 ms 1048 KB Output is correct
17 Correct 145 ms 6244 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -