# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1105465 | 2024-10-26T13:12:22 Z | borisAngelov | Strange Device (APIO19_strange_device) | C++17 | 321 ms | 48808 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; 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 (newL < newR || (newL == newR && l == r)) { intervals.push_back({newL, newR}); } else { intervals.push_back({newL, MOD - 1}); intervals.push_back({0, newR}); } } } /*if (hasPeriod == false) { 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 | 1104 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 | 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 | 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 | 336 KB | Output is correct |
2 | Correct | 272 ms | 37948 KB | Output is correct |
3 | Correct | 286 ms | 18864 KB | Output is correct |
4 | Correct | 298 ms | 48808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 272 ms | 37948 KB | Output is correct |
3 | Correct | 286 ms | 18864 KB | Output is correct |
4 | Correct | 298 ms | 48808 KB | Output is correct |
5 | Correct | 1 ms | 336 KB | Output is correct |
6 | Correct | 278 ms | 18864 KB | Output is correct |
7 | Correct | 258 ms | 37552 KB | Output is correct |
8 | Correct | 309 ms | 18864 KB | Output is correct |
9 | Correct | 293 ms | 19052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 272 ms | 37948 KB | Output is correct |
3 | Correct | 286 ms | 18864 KB | Output is correct |
4 | Correct | 298 ms | 48808 KB | Output is correct |
5 | Correct | 1 ms | 336 KB | Output is correct |
6 | Correct | 31 ms | 6348 KB | Output is correct |
7 | Correct | 28 ms | 3532 KB | Output is correct |
8 | Correct | 25 ms | 3532 KB | Output is correct |
9 | Correct | 30 ms | 3532 KB | Output is correct |
10 | Correct | 32 ms | 6204 KB | Output is correct |
11 | Correct | 35 ms | 6100 KB | Output is correct |
12 | Correct | 31 ms | 3532 KB | Output is correct |
13 | Correct | 35 ms | 6084 KB | Output is correct |
14 | Correct | 30 ms | 6208 KB | Output is correct |
15 | Incorrect | 31 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 | 35 ms | 5580 KB | Output is correct |
3 | Correct | 58 ms | 6080 KB | Output is correct |
4 | Correct | 321 ms | 21840 KB | Output is correct |
5 | Correct | 33 ms | 5684 KB | Output is correct |
6 | Correct | 54 ms | 5572 KB | Output is correct |
7 | Correct | 38 ms | 4532 KB | Output is correct |
8 | Correct | 58 ms | 5644 KB | Output is correct |
9 | Correct | 31 ms | 2508 KB | Output is correct |
10 | Correct | 45 ms | 4548 KB | Output is correct |
11 | Correct | 31 ms | 3700 KB | Output is correct |
12 | Correct | 28 ms | 2508 KB | Output is correct |
13 | Correct | 35 ms | 6084 KB | Output is correct |
14 | Incorrect | 299 ms | 37552 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 | 1104 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |