oj.uz

Submission #1001203

# Submission time Handle Problem Language Result Execution time Memory
1001203 2024-06-18T16:58:02 Z ParsaGolestani Strange Device (APIO19_strange_device) C++17
10 / 100
 670 ms 125632 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;

const int N = 1'000'000;

ll n, a, b, l[N + 10], r[N + 10];
set<pair<pl, pl>> s;
vector<pair<pl, pl>> vec;

void readInput() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];
}

void addSeg(pl l, pl r) {
    //cout << l.first << ' ' << l.second << " | " << r.first << ' ' << r.second << endl;
    vec.push_back({l, r});
}

void addS(pl l, pl r) {
    while (true) {
        auto au = s.lower_bound({l, {0ll, 0ll}});
        if (au != s.end() && au -> first <= r) {
            r = max(r, au -> second);
            s.erase(au);
        }
        else {
            s.insert({l, r});
            break;
        }
    }
}

void addAll() {
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for (auto [l, r]: vec)
        addS(l, r);
}

pl getP(ll x) {
    ll q = x / b;
    ll r = x % b;
    return {((b + 1) % a == 0? 0: q % a), r};
}

ll getLen(pl x, pl y) {
    ll lenX = y.first - x.first;
    return lenX * b - x.second + y.second + 1;
}

void calcS() {
    pl mxP = ((b + 1) % a? make_pair(a - 1, b - 1): make_pair(0ll, b - 1));
    for (int i = 1; i <= n; i++) {
        ll len = r[i] - l[i] + 1;
        if (len / b >= a || ((b + 1) % a == 0 && len >= b)) {
            s.insert({{0ll, 0ll}, mxP});
            addAll();
            return;
        }
    }
    for (int i = 1; i <= n; i++) {
        pl f = getP(l[i]);
        pl g = getP(r[i]);
        if (g < f) {
            addSeg({0ll, 0ll}, g);
            addSeg(f, mxP);
        }
        else
            addSeg(f, g);
    }
    addAll();
}

void calcAnswer() {
    ll ans = 0;
    while (s.size()) {
        ans += getLen(s.begin() -> first, s.begin() -> second);
        s.erase(s.begin());
    }
    cout << ans << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcS();
    calcAnswer();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 5 ms 3548 KB Output is correct
3 Correct 5 ms 3472 KB Output is correct
4 Incorrect 0 ms 2396 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 249 ms 49048 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 621 ms 125492 KB Output is correct
3 Incorrect 567 ms 125560 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 2648 KB Output is correct
2 Correct 621 ms 125492 KB Output is correct
3 Incorrect 567 ms 125560 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 2648 KB Output is correct
2 Correct 621 ms 125492 KB Output is correct
3 Incorrect 567 ms 125560 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 2396 KB Output is correct
2 Correct 56 ms 15748 KB Output is correct
3 Correct 57 ms 17528 KB Output is correct
4 Correct 670 ms 125596 KB Output is correct
5 Correct 51 ms 17600 KB Output is correct
6 Correct 57 ms 18664 KB Output is correct
7 Correct 65 ms 17596 KB Output is correct
8 Correct 59 ms 18368 KB Output is correct
9 Correct 61 ms 17704 KB Output is correct
10 Correct 57 ms 17608 KB Output is correct
11 Correct 54 ms 18396 KB Output is correct
12 Correct 63 ms 17664 KB Output is correct
13 Correct 56 ms 17596 KB Output is correct
14 Correct 646 ms 125632 KB Output is correct
15 Incorrect 57 ms 17596 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 2392 KB Output is correct
2 Correct 5 ms 3548 KB Output is correct
3 Correct 5 ms 3472 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -