oj.uz

답안 #1001234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1001234 2024-06-18T17:19:22 Z ParsaGolestani 이상한 기계 (APIO19_strange_device) C++17
60 / 100
 659 ms 164256 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;

ll gcd(ll a, ll b) {
    return b? gcd(b, a % b): a;
}

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 5 ms 4060 KB Output is correct
3 Correct 5 ms 4064 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2480 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2652 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Incorrect 0 ms 2396 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 231 ms 74688 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 541 ms 163624 KB Output is correct
3 Correct 569 ms 163492 KB Output is correct
4 Correct 557 ms 164256 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 541 ms 163624 KB Output is correct
3 Correct 569 ms 163492 KB Output is correct
4 Correct 557 ms 164256 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 555 ms 163512 KB Output is correct
7 Correct 553 ms 163236 KB Output is correct
8 Correct 568 ms 164012 KB Output is correct
9 Correct 621 ms 164008 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 541 ms 163624 KB Output is correct
3 Correct 569 ms 163492 KB Output is correct
4 Correct 557 ms 164256 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 50 ms 21624 KB Output is correct
7 Correct 55 ms 21540 KB Output is correct
8 Correct 52 ms 21192 KB Output is correct
9 Correct 61 ms 22212 KB Output is correct
10 Correct 52 ms 21440 KB Output is correct
11 Correct 53 ms 21940 KB Output is correct
12 Correct 50 ms 21324 KB Output is correct
13 Correct 55 ms 21704 KB Output is correct
14 Correct 53 ms 21320 KB Output is correct
15 Correct 60 ms 21468 KB Output is correct
16 Correct 57 ms 21348 KB Output is correct
17 Correct 54 ms 21440 KB Output is correct
18 Correct 544 ms 163748 KB Output is correct
19 Correct 536 ms 162884 KB Output is correct
20 Correct 629 ms 164096 KB Output is correct
21 Correct 56 ms 21448 KB Output is correct
22 Correct 53 ms 22236 KB Output is correct
23 Correct 101 ms 40532 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 56 ms 22000 KB Output is correct
3 Correct 58 ms 21448 KB Output is correct
4 Correct 659 ms 162740 KB Output is correct
5 Correct 80 ms 21440 KB Output is correct
6 Correct 61 ms 21460 KB Output is correct
7 Correct 62 ms 21440 KB Output is correct
8 Correct 57 ms 21336 KB Output is correct
9 Correct 57 ms 21440 KB Output is correct
10 Correct 57 ms 21452 KB Output is correct
11 Correct 58 ms 21400 KB Output is correct
12 Correct 53 ms 21952 KB Output is correct
13 Correct 60 ms 21696 KB Output is correct
14 Correct 583 ms 163644 KB Output is correct
15 Correct 49 ms 20924 KB Output is correct
16 Correct 531 ms 163168 KB Output is correct
17 Correct 507 ms 164196 KB Output is correct
18 Correct 0 ms 2392 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 5 ms 4060 KB Output is correct
3 Correct 5 ms 4064 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2480 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2652 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Incorrect 0 ms 2396 KB Output isn't correct
13 Halted 0 ms 0 KB -