oj.uz

Submission #554219

# Submission time Handle Problem Language Result Execution time Memory
554219 2022-04-28T03:15:53 Z happypotato Strange Device (APIO19_strange_device) C++17
65 / 100
 1481 ms 33556 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
    while (b) b ^= a ^= b ^= a %= b;
    return a;
}
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int g = gcd(a, b + 1);
    priority_queue<pair<int, bool>, vector<pair<int, bool> >, greater<pair<int, bool> > > pq;
    int mod;
    if (log2(a) + log2(b) - log2(g) > log2(2e18)) mod = 2e18;
    else mod = a / g * b;
    while (n--) {
        int l, r;
        cin >> l >> r;
        l %= mod; r %= mod;
        if (l > r) {
            pq.push({l, true});
            pq.push({mod, false});
            pq.push({0, true});
            pq.push({r + 1, false});
        } else {
            pq.push({l, true});
            pq.push({r + 1, false});
        }
    }
    int prev = 0, ans = 0;
    int cnt = 0;
    while (!pq.empty()) {
        pair<int, bool> cur = pq.top();
        pq.pop();
        if (cnt) ans += cur.first - prev;
        prev = cur.first;
        cnt += (cur.second ? 1 : -1);
    }
    cout << ans << endl;
}
signed main() {
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 16 ms 1044 KB Output is correct
3 Correct 16 ms 952 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 15 ms 1076 KB Output is correct
17 Correct 144 ms 4760 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 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 344 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 1002 ms 33348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1445 ms 33428 KB Output is correct
3 Correct 1439 ms 33392 KB Output is correct
4 Correct 1426 ms 33324 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1445 ms 33428 KB Output is correct
3 Correct 1439 ms 33392 KB Output is correct
4 Correct 1426 ms 33324 KB Output is correct
5 Correct 0 ms 280 KB Output is correct
6 Correct 1417 ms 33416 KB Output is correct
7 Correct 1429 ms 33468 KB Output is correct
8 Correct 1451 ms 33420 KB Output is correct
9 Correct 1423 ms 33420 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1445 ms 33428 KB Output is correct
3 Correct 1439 ms 33392 KB Output is correct
4 Correct 1426 ms 33324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 153 ms 4760 KB Output is correct
7 Correct 149 ms 4760 KB Output is correct
8 Correct 146 ms 4748 KB Output is correct
9 Correct 147 ms 4768 KB Output is correct
10 Correct 147 ms 4704 KB Output is correct
11 Correct 144 ms 4760 KB Output is correct
12 Correct 145 ms 4724 KB Output is correct
13 Correct 142 ms 4744 KB Output is correct
14 Correct 145 ms 4716 KB Output is correct
15 Correct 142 ms 4668 KB Output is correct
16 Correct 162 ms 4712 KB Output is correct
17 Correct 149 ms 4772 KB Output is correct
18 Correct 1416 ms 33556 KB Output is correct
19 Correct 1425 ms 33384 KB Output is correct
20 Correct 1481 ms 33384 KB Output is correct
21 Correct 144 ms 4720 KB Output is correct
22 Correct 147 ms 4756 KB Output is correct
23 Correct 470 ms 17204 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 145 ms 4664 KB Output is correct
3 Correct 143 ms 4844 KB Output is correct
4 Correct 1421 ms 33244 KB Output is correct
5 Correct 146 ms 4992 KB Output is correct
6 Correct 142 ms 4920 KB Output is correct
7 Correct 141 ms 4868 KB Output is correct
8 Correct 143 ms 4836 KB Output is correct
9 Correct 147 ms 4856 KB Output is correct
10 Correct 142 ms 4788 KB Output is correct
11 Correct 147 ms 4916 KB Output is correct
12 Correct 145 ms 4888 KB Output is correct
13 Correct 145 ms 4764 KB Output is correct
14 Correct 1431 ms 33324 KB Output is correct
15 Correct 146 ms 4664 KB Output is correct
16 Correct 1429 ms 33396 KB Output is correct
17 Correct 1437 ms 33444 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 16 ms 1044 KB Output is correct
3 Correct 16 ms 952 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 15 ms 1076 KB Output is correct
17 Correct 144 ms 4760 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -