제출 #1001203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001203		ParsaGolestani	이상한 기계 (APIO19_strange_device)	C++17	10 / 100	670 ms	125632 KiB

strange_device

#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
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30