oj.uz

Submission #1044746

# Submission time Handle Problem Language Result Execution time Memory
1044746 2024-08-05T13:07:46 Z vjudge1 Strange Device (APIO19_strange_device) C++17
10 / 100
 500 ms 62928 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) {
        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 4 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 348 KB Output is correct
2 Correct 1 ms 348 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 436 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 405 ms 62916 KB Output is correct
3 Incorrect 500 ms 62928 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 344 KB Output is correct
2 Correct 405 ms 62916 KB Output is correct
3 Incorrect 500 ms 62928 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 344 KB Output is correct
2 Correct 405 ms 62916 KB Output is correct
3 Incorrect 500 ms 62928 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 348 KB Output is correct
2 Correct 39 ms 6576 KB Output is correct
3 Correct 43 ms 6616 KB Output is correct
4 Correct 454 ms 62820 KB Output is correct
5 Correct 39 ms 6484 KB Output is correct
6 Correct 42 ms 6484 KB Output is correct
7 Correct 43 ms 6480 KB Output is correct
8 Correct 41 ms 6484 KB Output is correct
9 Correct 39 ms 6484 KB Output is correct
10 Correct 34 ms 6572 KB Output is correct
11 Correct 43 ms 6480 KB Output is correct
12 Correct 34 ms 6488 KB Output is correct
13 Correct 39 ms 6736 KB Output is correct
14 Correct 470 ms 62880 KB Output is correct
15 Incorrect 38 ms 6600 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 4 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 -