oj.uz

Submission #554214

# Submission time Handle Problem Language Result Execution time Memory
554214 2022-04-28T03:05:09 Z happypotato Strange Device (APIO19_strange_device) C++17
5 / 100
 1454 ms 68940 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    if (b >= 3e18 / a) {
        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 0 ms 212 KB Output is correct
2 Correct 15 ms 1184 KB Output is correct
3 Correct 15 ms 1176 KB Output is correct
4 Incorrect 1 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 0 ms 212 KB Output is correct
2 Incorrect 1 ms 296 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 316 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 1067 ms 57012 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 1445 ms 33348 KB Output is correct
3 Incorrect 1435 ms 33240 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 1445 ms 33348 KB Output is correct
3 Incorrect 1435 ms 33240 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 1445 ms 33348 KB Output is correct
3 Incorrect 1435 ms 33240 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 150 ms 4696 KB Output is correct
3 Correct 149 ms 4700 KB Output is correct
4 Correct 1454 ms 33272 KB Output is correct
5 Correct 144 ms 4772 KB Output is correct
6 Correct 146 ms 4680 KB Output is correct
7 Correct 140 ms 4708 KB Output is correct
8 Correct 143 ms 4752 KB Output is correct
9 Correct 145 ms 4732 KB Output is correct
10 Correct 142 ms 4744 KB Output is correct
11 Correct 142 ms 4688 KB Output is correct
12 Correct 144 ms 4812 KB Output is correct
13 Correct 147 ms 7236 KB Output is correct
14 Correct 1437 ms 68940 KB Output is correct
15 Incorrect 148 ms 7160 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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