oj.uz

Submission #934294

# Submission time Handle Problem Language Result Execution time Memory
934294 2024-02-27T06:28:08 Z vjudge1 Strange Device (APIO19_strange_device) C++17
15 / 100
 412 ms 87756 KB 
// Problem: A - Strange Device
// Contest: Virtual Judge - 2024-02-27 APIO Simulation
// URL: https://vjudge.net/contest/612540#problem/A
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define what_is(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n; ll A, B;
const int MAXN = 1000010;
ll L[MAXN], R[MAXN];

void subtask1() {
	set<pair<ll, ll>> ans;
	for (int i = 1; i <= n; i++) {
		for (ll j = L[i]; j <= R[i]; j++) {
			ll x = (j + j / B) % A;
			ll y = j % B;
			ans.insert({x, y});
		}
	}
	cout << sz(ans) << endl;
}

void subtask4() {
	bool halved = false;
	if (A % 2 == 0) {
		A /= 2;
		halved = true;
	}
	bool full = false;
	vector<pair<ll, int>> events;
	for (int i = 1; i <= n; i++) {
		ll l = L[i] % A, r = R[i] % A;
		if (R[i] - L[i] + 1 >= A) {
			full = true;
			break;
		}
		if (l <= r) {
			events.push_back({l, -1});
			events.push_back({r + 1, 1});
		} else {
			events.push_back({0, -1});
			events.push_back({r + 1, 1});
			events.push_back({l, -1});
			events.push_back({A, 1});
		}
	}
	
	if (full) {
		cout << A << endl;
		if (halved) A *= 2;
		return;
	}
	
	ll ans = 0;
	int open = 0;
	sort(all(events));
	ll cur_time = 0;
	for (auto ev : events) {
		// cout << ev.first << " " << ev.second << endl;
		ll passed = ev.first - cur_time;
		if (open > 0) ans += passed;
		open -= ev.second;
		cur_time = ev.first;
	}
	cout << ans << endl;
	
	if (halved) A *= 2;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> A >> B;
	ll S = 0, SL = 0;
	for (int i = 1; i <= n; i++) {
		cin >> L[i] >> R[i];
		S += (R[i] - L[i] + 1);
		SL = max(SL, R[i] - L[i] + 1);
	}
	if (S <= 1000000) subtask1();
	else if (B == 1) subtask4();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 41 ms 14676 KB Output is correct
3 Correct 51 ms 20052 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 6 ms 3284 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 34 ms 9104 KB Output is correct
16 Correct 22 ms 8796 KB Output is correct
17 Correct 42 ms 12892 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 113 ms 34424 KB Output is correct
3 Correct 158 ms 34128 KB Output is correct
4 Correct 97 ms 32688 KB Output is correct
5 Incorrect 185 ms 41188 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 394 ms 49388 KB Output is correct
3 Correct 412 ms 86488 KB Output is correct
4 Correct 388 ms 87756 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 394 ms 49388 KB Output is correct
3 Correct 412 ms 86488 KB Output is correct
4 Correct 388 ms 87756 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Incorrect 231 ms 52956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 394 ms 49388 KB Output is correct
3 Correct 412 ms 86488 KB Output is correct
4 Correct 388 ms 87756 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Incorrect 24 ms 10324 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Incorrect 24 ms 10352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 41 ms 14676 KB Output is correct
3 Correct 51 ms 20052 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 6 ms 3284 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 34 ms 9104 KB Output is correct
16 Correct 22 ms 8796 KB Output is correct
17 Correct 42 ms 12892 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Incorrect 1 ms 2396 KB Output isn't correct
21 Halted 0 ms 0 KB -