oj.uz

Submission #1044749

# Submission time Handle Problem Language Result Execution time Memory
1044749 2024-08-05T13:09:41 Z vjudge1 Strange Device (APIO19_strange_device) C++17
10 / 100
 473 ms 63036 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 3e4 + 100;

#define int long long
set<pair<int,int>> st;
void add_seg(int l, int r) {
    if (st.size()) {
        auto x = st.lower_bound(make_pair(l, 0));
        if (x != st.begin() && (*prev(x)).s >= l)
            x--;

        while (x != st.end() && (*x).f <= r) {
            l = min(l, (*x).f);
            r = max(r, (*x).s);
            x = st.erase(x);
        }
    }
    st.insert({l, r});
}

signed main() {
    fast
    ll n, A, B;
    cin >> n >> A >> B;

    if (1e9 * 1LL * 1e9 / A <= B + 1) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l, r;
            cin >> l >> r;
            add_seg(l, r);
        }

        for (auto u : st)
            ans += u.s - u.f + 1;
        cout << ans << "\n";
        return 0;
    }

    A *= B;

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;

        int x = l % A;
        int y = r % A;
        if (y < x || r - l + 1 >= A) {
            add_seg(x, A-1);
            add_seg(0, y);
        } else
            add_seg(x, y);
    }

    ll ans = 0;
    for (auto u : st)
        ans += u.s - u.f + 1;
    cout << ans << "\n";
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 148 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 392 ms 62900 KB Output is correct
3 Incorrect 430 ms 62800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 392 ms 62900 KB Output is correct
3 Incorrect 430 ms 62800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 392 ms 62900 KB Output is correct
3 Incorrect 430 ms 62800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 41 ms 6492 KB Output is correct
3 Correct 48 ms 6588 KB Output is correct
4 Correct 458 ms 63036 KB Output is correct
5 Correct 39 ms 6672 KB Output is correct
6 Correct 41 ms 6544 KB Output is correct
7 Correct 47 ms 6584 KB Output is correct
8 Correct 45 ms 6628 KB Output is correct
9 Correct 41 ms 6548 KB Output is correct
10 Correct 35 ms 6520 KB Output is correct
11 Correct 37 ms 6588 KB Output is correct
12 Correct 35 ms 6492 KB Output is correct
13 Correct 43 ms 6488 KB Output is correct
14 Correct 473 ms 62876 KB Output is correct
15 Incorrect 39 ms 6484 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 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -