제출 #1324215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324215		sh_qaxxorov_571	이상한 기계 (APIO19_strange_device)	C++20	100 / 100	324 ms	16984 KiB

strange_device

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef __int128_t int128; // Juda katta sonlar uchun

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long A, B;
    cin >> n >> A >> B;

    // Davrni hisoblash: T = (A / gcd(A, B + 1)) * B
    long long common = gcd(A, B + 1);
    int128 T_val = (int128)A / common * B;
    long long T;
    const long long INF = 2e18; // Maksimal chegara

    if (T_val >= INF) T = INF;
    else T = (long long)T_val;

    vector<pair<long long, long long>> segments;

    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;

        if (r - l + 1 >= T) {
            // Agar oraliq davrdan katta bo'lsa, hamma nuqtalar qoplanadi
            cout << (long long)T << endl;
            return 0;
        }

        l %= T;
        r %= T;

        if (l <= r) {
            segments.push_back({l, r});
        } else {
            // Davrdan o'tib ketgan qismini ikkiga bo'lamiz
            segments.push_back({l, T - 1});
            segments.push_back({0, r});
        }
    }

    // Segmentlarni birlashtirish (Interval Merging)
    sort(segments.begin(), segments.end());

    long long total_ans = 0;
    if (!segments.empty()) {
        long long curL = segments[0].first;
        long long curR = segments[0].second;

        for (size_t i = 1; i < segments.size(); i++) {
            if (segments[i].first <= curR) {
                curR = max(curR, segments[i].second);
            } else {
                total_ans += (curR - curL + 1);
                curL = segments[i].first;
                curR = segments[i].second;
            }
        }
        total_ans += (curR - curL + 1);
    }

    cout << total_ans << endl;

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30