oj.uz

Submission #732053

# Submission time Handle Problem Language Result Execution time Memory
732053 2023-04-28T10:08:51 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
35 / 100
 2085 ms 49060 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) {
	return b ? gcd(b, a % b) : a;
}

//x(B+1) == 0
//x(b+1)
main() {
	cin >> n >> A >> B;
	segs.resize(n);
	ll cycle = 1e18;
	ll C = A / (gcd(B + 1, A));
	if(((B * C) / C == B) && ((B * C) / B == C)) 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:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | 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 1004 KB Output is correct
3 Correct 14 ms 1100 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1104 KB Output is correct
17 Correct 143 ms 6076 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 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 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 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 340 KB Output is correct
5 Correct 975 ms 48960 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1438 ms 48936 KB Output is correct
3 Correct 1405 ms 48916 KB Output is correct
4 Correct 1375 ms 48920 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1438 ms 48936 KB Output is correct
3 Correct 1405 ms 48916 KB Output is correct
4 Correct 1375 ms 48920 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2085 ms 48856 KB Output is correct
7 Correct 1414 ms 48884 KB Output is correct
8 Correct 1392 ms 48952 KB Output is correct
9 Correct 1510 ms 48864 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1438 ms 48936 KB Output is correct
3 Correct 1405 ms 48916 KB Output is correct
4 Correct 1375 ms 48920 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 162 ms 6000 KB Output is correct
7 Correct 159 ms 6100 KB Output is correct
8 Correct 140 ms 6040 KB Output is correct
9 Correct 148 ms 6048 KB Output is correct
10 Correct 147 ms 6028 KB Output is correct
11 Correct 137 ms 6068 KB Output is correct
12 Correct 143 ms 6088 KB Output is correct
13 Correct 143 ms 6080 KB Output is correct
14 Correct 166 ms 6000 KB Output is correct
15 Correct 145 ms 6076 KB Output is correct
16 Correct 150 ms 6056 KB Output is correct
17 Correct 139 ms 6056 KB Output is correct
18 Correct 1460 ms 48792 KB Output is correct
19 Correct 1422 ms 49016 KB Output is correct
20 Correct 1524 ms 49060 KB Output is correct
21 Correct 145 ms 5976 KB Output is correct
22 Correct 139 ms 6096 KB Output is correct
23 Correct 440 ms 22100 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 144 ms 6148 KB Output is correct
3 Correct 148 ms 6064 KB Output is correct
4 Correct 1559 ms 48916 KB Output is correct
5 Correct 172 ms 6052 KB Output is correct
6 Correct 150 ms 6024 KB Output is correct
7 Correct 144 ms 6068 KB Output is correct
8 Correct 154 ms 6192 KB Output is correct
9 Correct 146 ms 6076 KB Output is correct
10 Correct 141 ms 5992 KB Output is correct
11 Correct 150 ms 6032 KB Output is correct
12 Correct 149 ms 6048 KB Output is correct
13 Correct 153 ms 5980 KB Output is correct
14 Correct 1508 ms 48912 KB Output is correct
15 Correct 146 ms 6080 KB Output is correct
16 Correct 1362 ms 48928 KB Output is correct
17 Correct 1468 ms 48992 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 1004 KB Output is correct
3 Correct 14 ms 1100 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1104 KB Output is correct
17 Correct 143 ms 6076 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -