Submission #1167728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167728		unknownproblem	Strange Device (APIO19_strange_device)	C++20	100 / 100	345 ms	64784 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
 

string toString(__int128 x) {
    if(x == 0) return "0";
    bool neg = false;
    if(x < 0) { neg = true; x = -x; }
    string s;
    while(x > 0) {
        int d = (int)(x % 10);
        s.push_back('0' + d);
        x /= 10;
    }
    if(neg) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}
 
ostream& operator<<(ostream &out, const __int128 &x) {
    out << toString(x);
    return out;
}

struct Interval {
    __int128 l, r; // 0 <= l <= r < T
};
 
long long gcd_ll(long long a, long long b){
    while(b){
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    long long A_ll, B_ll;
    cin >> n >> A_ll >> B_ll;
    __int128 A = A_ll, B = B_ll;
 
    vector<pair<__int128, __int128>> intervals;
    intervals.reserve(n);
    for (int i = 0; i < n; i++){
        long long l_ll, r_ll;
        cin >> l_ll >> r_ll;
        __int128 l = l_ll, r = r_ll;
        intervals.push_back({l, r});
    }
 
    long long Bplus1_ll = B_ll + 1;
    long long g_ll = gcd_ll(A_ll, Bplus1_ll);
    __int128 p = A / g_ll;
    __int128 T = p * B;
 
    vector<Interval> modIntervals;
    bool coversFull = false;
    for(auto &seg : intervals){
        __int128 l = seg.first, r = seg.second;
        __int128 len = r - l + 1;
        if(len >= T) {
            coversFull = true;
            break;
        }
        __int128 start = l % T;
        __int128 end = (l + len - 1) % T;
        if(start <= end) {
            modIntervals.push_back({start, end});
        } else {
            modIntervals.push_back({start, T - 1});
            modIntervals.push_back({0, end});
        }
    }
 
    __int128 result = 0;
    if(coversFull){
        result = T; 
    } else {
        sort(modIntervals.begin(), modIntervals.end(), [](const Interval &a, const Interval &b){
            return a.l < b.l;
        });

        __int128 curL = modIntervals[0].l, curR = modIntervals[0].r;
        for (size_t i = 1; i < modIntervals.size(); i++){
            if(modIntervals[i].l <= curR + 1) {
                curR = max(curR, modIntervals[i].r);
            } else {
                result += (curR - curL + 1);
                curL = modIntervals[i].l;
                curR = modIntervals[i].r;
            }
        }
        result += (curR - curL + 1);
    }
 
    cout << result << "\n";
    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