oj.uz

Submission #554215

# Submission time Handle Problem Language Result Execution time Memory
554215 2022-04-28T03:07:26 Z happypotato Strange Device (APIO19_strange_device) C++17
5 / 100
 1490 ms 33404 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    if (log2(a) + log2(b) > log2(4e18)) {
        int ans = 0;
        while (n--) {
            int l, r;
            cin >> l >> r;
            ans += r - l + 1;
        }
        cout << ans << endl;
        return;
    }
    priority_queue<pair<int, bool>, vector<pair<int, bool> >, greater<pair<int, bool> > > pq;
    int mod = a * 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 15 ms 1104 KB Output is correct
3 Correct 15 ms 1136 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 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 300 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 368 KB Output is correct
5 Correct 1026 ms 33196 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 1458 ms 33260 KB Output is correct
3 Incorrect 1490 ms 33296 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 1458 ms 33260 KB Output is correct
3 Incorrect 1490 ms 33296 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 1458 ms 33260 KB Output is correct
3 Incorrect 1490 ms 33296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 149 ms 4760 KB Output is correct
3 Correct 155 ms 4688 KB Output is correct
4 Correct 1410 ms 33348 KB Output is correct
5 Correct 144 ms 4712 KB Output is correct
6 Correct 143 ms 4828 KB Output is correct
7 Correct 139 ms 4740 KB Output is correct
8 Correct 142 ms 4796 KB Output is correct
9 Correct 148 ms 4736 KB Output is correct
10 Correct 143 ms 4792 KB Output is correct
11 Correct 139 ms 4664 KB Output is correct
12 Correct 145 ms 4664 KB Output is correct
13 Correct 143 ms 4708 KB Output is correct
14 Correct 1418 ms 33404 KB Output is correct
15 Incorrect 141 ms 4708 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 15 ms 1104 KB Output is correct
3 Correct 15 ms 1136 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -