oj.uz

Submission #1001193

# Submission time Handle Problem Language Result Execution time Memory
1001193 2024-06-18T16:53:12 Z ParsaGolestani Strange Device (APIO19_strange_device) C++17
10 / 100
 681 ms 162804 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});
            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 1 ms 2396 KB Output is correct
2 Correct 5 ms 3928 KB Output is correct
3 Correct 5 ms 4060 KB Output is correct
4 Incorrect 1 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 1 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 1 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 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2784 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 255 ms 74172 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 619 ms 162748 KB Output is correct
3 Incorrect 620 ms 162804 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 2396 KB Output is correct
2 Correct 619 ms 162748 KB Output is correct
3 Incorrect 620 ms 162804 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 2396 KB Output is correct
2 Correct 619 ms 162748 KB Output is correct
3 Incorrect 620 ms 162804 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 2392 KB Output is correct
2 Correct 57 ms 21192 KB Output is correct
3 Correct 59 ms 21448 KB Output is correct
4 Correct 681 ms 162760 KB Output is correct
5 Correct 59 ms 21952 KB Output is correct
6 Correct 59 ms 21248 KB Output is correct
7 Correct 56 ms 21624 KB Output is correct
8 Correct 56 ms 21436 KB Output is correct
9 Correct 56 ms 21704 KB Output is correct
10 Correct 62 ms 21952 KB Output is correct
11 Correct 57 ms 21440 KB Output is correct
12 Correct 51 ms 21468 KB Output is correct
13 Correct 60 ms 21392 KB Output is correct
14 Correct 664 ms 162760 KB Output is correct
15 Incorrect 59 ms 21440 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 2396 KB Output is correct
2 Correct 5 ms 3928 KB Output is correct
3 Correct 5 ms 4060 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -