oj.uz

Submission #732048

# Submission time Handle Problem Language Result Execution time Memory
732048 2023-04-28T09:58:56 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
35 / 100
 1565 ms 49092 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
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:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | 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 1008 KB Output is correct
3 Correct 19 ms 1104 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 1 ms 212 KB Output is correct
11 Correct 0 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 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1004 KB Output is correct
17 Correct 140 ms 5972 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 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 3 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 961 ms 48900 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1450 ms 48992 KB Output is correct
3 Correct 1472 ms 48904 KB Output is correct
4 Correct 1408 ms 49092 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1450 ms 48992 KB Output is correct
3 Correct 1472 ms 48904 KB Output is correct
4 Correct 1408 ms 49092 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1431 ms 48896 KB Output is correct
7 Correct 1420 ms 49076 KB Output is correct
8 Correct 1399 ms 48940 KB Output is correct
9 Correct 1565 ms 49004 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1450 ms 48992 KB Output is correct
3 Correct 1472 ms 48904 KB Output is correct
4 Correct 1408 ms 49092 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 139 ms 6144 KB Output is correct
7 Correct 135 ms 5988 KB Output is correct
8 Correct 142 ms 6000 KB Output is correct
9 Correct 158 ms 6200 KB Output is correct
10 Correct 142 ms 6084 KB Output is correct
11 Correct 139 ms 6024 KB Output is correct
12 Correct 135 ms 6064 KB Output is correct
13 Correct 140 ms 6104 KB Output is correct
14 Correct 131 ms 6076 KB Output is correct
15 Correct 137 ms 6092 KB Output is correct
16 Correct 146 ms 6056 KB Output is correct
17 Correct 136 ms 5980 KB Output is correct
18 Correct 1414 ms 49056 KB Output is correct
19 Correct 1386 ms 48912 KB Output is correct
20 Correct 1561 ms 48848 KB Output is correct
21 Correct 150 ms 6100 KB Output is correct
22 Correct 145 ms 6024 KB Output is correct
23 Correct 428 ms 22148 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 156 ms 6092 KB Output is correct
3 Correct 153 ms 6028 KB Output is correct
4 Correct 1523 ms 48848 KB Output is correct
5 Correct 138 ms 6060 KB Output is correct
6 Correct 147 ms 6076 KB Output is correct
7 Correct 153 ms 6012 KB Output is correct
8 Correct 161 ms 6180 KB Output is correct
9 Correct 145 ms 6116 KB Output is correct
10 Correct 148 ms 6052 KB Output is correct
11 Correct 154 ms 6056 KB Output is correct
12 Correct 135 ms 6104 KB Output is correct
13 Correct 146 ms 6100 KB Output is correct
14 Correct 1561 ms 48920 KB Output is correct
15 Correct 140 ms 6128 KB Output is correct
16 Correct 1335 ms 48908 KB Output is correct
17 Correct 1416 ms 48816 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 0 ms 212 KB Output is correct
2 Correct 14 ms 1008 KB Output is correct
3 Correct 19 ms 1104 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 1 ms 212 KB Output is correct
11 Correct 0 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 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1004 KB Output is correct
17 Correct 140 ms 5972 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -