# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1105474 | 2024-10-26T13:23:04 Z | borisAngelov | Strange Device (APIO19_strange_device) | C++17 | 305 ms | 19024 KB |
#include <bits/stdc++.h> using namespace std; const long long MAXMOD = 1e18 + 7; int n; long long a, b; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> a >> b; long long MOD = a / __gcd(a, b + 1); bool hasPeriod = true; if (MAXMOD / MOD < b) { hasPeriod = false; } else { MOD *= b; // a * b / gcd(a, b + 1) } vector<pair<long long, long long>> intervals; long long ans = 0; bool all = false; for (int i = 1; i <= n; ++i) { long long l, r; cin >> l >> r; if (hasPeriod == false) { ans += (r - l + 1); } else { long long newL = l % MOD; long long newR = r % MOD; if (l / MOD == r / MOD) { intervals.push_back({newL, newR}); } else if (l / MOD + 1 == r / MOD && newL > newR) { intervals.push_back({newL, MOD - 1}); intervals.push_back({0, newR}); } else { all = true; ans = MOD; } } } if (hasPeriod == false) { cout << 1/0 << endl; cout << ans << endl; return 0; } if (all == true) { cout << ans << endl; return 0; } sort(intervals.begin(), intervals.end()); long long from = intervals[0].first, to = intervals[0].second; for (int i = 1; i < intervals.size(); ++i) { if (intervals[i].first <= to) { to = intervals[i].second; } else { ans += (to - from + 1); from = intervals[i].first; to = intervals[i].second; } } ans += (to - from + 1); cout << ans << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Incorrect | 4 ms | 824 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 1 ms | 336 KB | Output is correct |
3 | Correct | 1 ms | 336 KB | Output is correct |
4 | Correct | 1 ms | 336 KB | Output is correct |
5 | Runtime error | 1 ms | 592 KB | Execution killed with signal 8 |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Incorrect | 1 ms | 336 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 289 ms | 19024 KB | Output is correct |
3 | Correct | 259 ms | 18864 KB | Output is correct |
4 | Correct | 297 ms | 19024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 289 ms | 19024 KB | Output is correct |
3 | Correct | 259 ms | 18864 KB | Output is correct |
4 | Correct | 297 ms | 19024 KB | Output is correct |
5 | Correct | 1 ms | 336 KB | Output is correct |
6 | Correct | 275 ms | 18864 KB | Output is correct |
7 | Correct | 271 ms | 18864 KB | Output is correct |
8 | Correct | 267 ms | 19008 KB | Output is correct |
9 | Correct | 300 ms | 18864 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 289 ms | 19024 KB | Output is correct |
3 | Correct | 259 ms | 18864 KB | Output is correct |
4 | Correct | 297 ms | 19024 KB | Output is correct |
5 | Correct | 1 ms | 336 KB | Output is correct |
6 | Correct | 28 ms | 3532 KB | Output is correct |
7 | Correct | 31 ms | 3472 KB | Output is correct |
8 | Correct | 29 ms | 3532 KB | Output is correct |
9 | Correct | 30 ms | 3532 KB | Output is correct |
10 | Correct | 28 ms | 3532 KB | Output is correct |
11 | Correct | 30 ms | 3532 KB | Output is correct |
12 | Correct | 28 ms | 3436 KB | Output is correct |
13 | Correct | 33 ms | 3528 KB | Output is correct |
14 | Correct | 28 ms | 3532 KB | Output is correct |
15 | Incorrect | 32 ms | 3532 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 31 ms | 3644 KB | Output is correct |
3 | Correct | 31 ms | 3524 KB | Output is correct |
4 | Correct | 304 ms | 19016 KB | Output is correct |
5 | Correct | 35 ms | 3532 KB | Output is correct |
6 | Correct | 31 ms | 3532 KB | Output is correct |
7 | Correct | 29 ms | 3532 KB | Output is correct |
8 | Correct | 32 ms | 3532 KB | Output is correct |
9 | Correct | 30 ms | 3532 KB | Output is correct |
10 | Correct | 32 ms | 3532 KB | Output is correct |
11 | Correct | 32 ms | 3548 KB | Output is correct |
12 | Correct | 27 ms | 3532 KB | Output is correct |
13 | Correct | 33 ms | 3660 KB | Output is correct |
14 | Incorrect | 305 ms | 18864 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Incorrect | 4 ms | 824 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |