oj.uz

Submission #732035

# Submission time Handle Problem Language Result Execution time Memory
732035 2023-04-28T09:31:16 Z US3RN4M3 Strange Device (APIO19_strange_device) C++17
5 / 100
 1565 ms 49080 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;
}

main() {
	cin >> n >> A >> B;
	segs.resize(n);
	ll cycle = 1e18;
	if((A * B) / B == A) cycle = A*B;
	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:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | 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 1104 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 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 1 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 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 364 KB Output is correct
5 Correct 948 ms 48908 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1426 ms 49000 KB Output is correct
3 Incorrect 1350 ms 49080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1426 ms 49000 KB Output is correct
3 Incorrect 1350 ms 49080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1426 ms 49000 KB Output is correct
3 Incorrect 1350 ms 49080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 154 ms 6076 KB Output is correct
3 Correct 149 ms 6104 KB Output is correct
4 Correct 1565 ms 48888 KB Output is correct
5 Correct 137 ms 6076 KB Output is correct
6 Correct 179 ms 6004 KB Output is correct
7 Correct 151 ms 6076 KB Output is correct
8 Correct 147 ms 6020 KB Output is correct
9 Correct 160 ms 6072 KB Output is correct
10 Correct 149 ms 6116 KB Output is correct
11 Correct 143 ms 6052 KB Output is correct
12 Correct 146 ms 6032 KB Output is correct
13 Correct 144 ms 6020 KB Output is correct
14 Correct 1518 ms 48856 KB Output is correct
15 Incorrect 148 ms 6140 KB Output isn't correct
16 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 1104 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -