oj.uz

Submission #732055

# Submission time Handle Problem Language Result Execution time Memory
732055 2023-04-28T10:10:58 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
35 / 100
 1955 ms 49772 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 C = A / (gcd(B + 1, A));
	assert(C);
	__int128 X = C;
	__int128 Y = B;
	__int128 Z = C * B;
	if(Z >= 1e18 + 10) {
		solve2();
		return 0;
	}
	ll cycle = C * B;
	assert(cycle % B == 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:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:26:11: warning: unused variable 'X' [-Wunused-variable]
   26 |  __int128 X = C;
      |           ^
strange_device.cpp:27:11: warning: unused variable 'Y' [-Wunused-variable]
   27 |  __int128 Y = B;
      |           ^

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 16 ms 1080 KB Output is correct
4 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 0 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 15 ms 1104 KB Output is correct
17 Correct 144 ms 6000 KB Output is correct
18 Runtime error 1 ms 340 KB Execution killed with signal 6
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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 340 KB Execution killed with signal 6
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 967 ms 48920 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 1379 ms 48920 KB Output is correct
3 Correct 1419 ms 48888 KB Output is correct
4 Correct 1387 ms 48956 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 1379 ms 48920 KB Output is correct
3 Correct 1419 ms 48888 KB Output is correct
4 Correct 1387 ms 48956 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1549 ms 49000 KB Output is correct
7 Correct 1372 ms 48920 KB Output is correct
8 Correct 1410 ms 48956 KB Output is correct
9 Correct 1501 ms 48952 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 1379 ms 48920 KB Output is correct
3 Correct 1419 ms 48888 KB Output is correct
4 Correct 1387 ms 48956 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 149 ms 6052 KB Output is correct
7 Correct 146 ms 6040 KB Output is correct
8 Correct 138 ms 6148 KB Output is correct
9 Correct 140 ms 5984 KB Output is correct
10 Correct 146 ms 6004 KB Output is correct
11 Correct 155 ms 6168 KB Output is correct
12 Correct 145 ms 6196 KB Output is correct
13 Correct 155 ms 6076 KB Output is correct
14 Correct 155 ms 6008 KB Output is correct
15 Correct 154 ms 5992 KB Output is correct
16 Correct 150 ms 5980 KB Output is correct
17 Correct 178 ms 6036 KB Output is correct
18 Correct 1591 ms 48988 KB Output is correct
19 Correct 1530 ms 48892 KB Output is correct
20 Correct 1708 ms 48936 KB Output is correct
21 Correct 170 ms 6264 KB Output is correct
22 Correct 149 ms 6292 KB Output is correct
23 Correct 543 ms 22428 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 169 ms 6440 KB Output is correct
3 Correct 170 ms 6248 KB Output is correct
4 Correct 1768 ms 49056 KB Output is correct
5 Correct 181 ms 6344 KB Output is correct
6 Correct 171 ms 6344 KB Output is correct
7 Correct 172 ms 6300 KB Output is correct
8 Correct 158 ms 6328 KB Output is correct
9 Correct 174 ms 6320 KB Output is correct
10 Correct 170 ms 6332 KB Output is correct
11 Correct 166 ms 6292 KB Output is correct
12 Correct 166 ms 6356 KB Output is correct
13 Correct 172 ms 6300 KB Output is correct
14 Correct 1955 ms 49080 KB Output is correct
15 Correct 211 ms 6472 KB Output is correct
16 Correct 1679 ms 49680 KB Output is correct
17 Correct 1675 ms 49772 KB Output is correct
18 Runtime error 1 ms 340 KB Execution killed with signal 6
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 16 ms 1080 KB Output is correct
4 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 0 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 15 ms 1104 KB Output is correct
17 Correct 144 ms 6000 KB Output is correct
18 Runtime error 1 ms 340 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -