Submission #1267389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267389		hoa208	Strange Device (APIO19_strange_device)	C++20	0 / 100	240 ms	589824 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 A, B;
    int n;
    if(!(cin >> A >> B >> n)) return 0;
    vector<pair<int64,int64>> intervals(n);
    for(int i=0;i<n;i++){
        int64 l,r; cin >> l >> r;
        intervals[i] = {l,r};
    }

    i128 L128 = (i128)A * (i128)B;
    // If L128 == 0 (shouldn't happen with A,B>=1) handle, but assume A,B>=1.

    // If any interval length >= L -> all residues appear.
    for(auto &it : intervals){
        i128 len = (i128)it.second - (i128)it.first + 1;
        if(L128 <= len){
            // print L128
            // cast to int64 if possible, otherwise print via i128 printing
            // but constraints should keep L128 <= 1e18 normally
            // we print as decimal:
            i128 val = L128;
            // print i128
            string s;
            if(val == 0) s = "0";
            else {
                bool neg = false;
                if(val < 0){ neg = true; val = -val; }
                while(val > 0){
                    int digit = (int)(val % 10);
                    s.push_back('0' + digit);
                    val /= 10;
                }
                if(neg) s.push_back('-');
                reverse(s.begin(), s.end());
            }
            cout << s << "\n";
            return 0;
        }
    }

    // Collect residue-segments on [0, L-1]
    vector<pair<int64,int64>> segs;
    for(auto &it : intervals){
        int64 l = it.first, r = it.second;
        // compute l_mod = l % L128, r_mod = r % L128
        i128 lm128 = (i128)l % L128;
        i128 rm128 = (i128)r % L128;
        int64 lm = (int64)lm128;
        int64 rm = (int64)rm128;
        if(lm <= rm){
            segs.emplace_back(lm, rm);
        }else{
            // wraps
            segs.emplace_back(lm, (int64)((i128)A*(i128)B - 1)); // L-1
            segs.emplace_back(0, rm);
        }
    }

    if(segs.empty()){
        cout << 0 << "\n";
        return 0;
    }

    // Note: L128 fits in i128. But segment endpoints are <= max(r) <= 1e18 so fit in int64.
    // Sort and merge
    sort(segs.begin(), segs.end());
    i128 total = 0;
    int64 curL = segs[0].first, curR = segs[0].second;
    for(size_t i=1;i<segs.size();++i){
        int64 s = segs[i].first, e = segs[i].second;
        if(s <= curR + 1){
            // overlap or touch
            if(e > curR) curR = e;
        } else {
            total += (i128)curR - (i128)curL + 1;
            curL = s; curR = e;
        }
    }
    total += (i128)curR - (i128)curL + 1;

    // total is <= L128 (we already ruled out any interval covering full L)
    // print total as decimal
    i128 val = total;
    string s;
    if(val == 0) s = "0";
    else {
        bool neg = false;
        if(val < 0){ neg = true; val = -val; }
        while(val > 0){
            int digit = (int)(val % 10);
            s.push_back('0' + digit);
            val /= 10;
        }
        if(neg) s.push_back('-');
        reverse(s.begin(), s.end());
    }
    cout << s << "\n";
    return 0;
}

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