Submission #974337

#	Time	Username	Problem	Language	Result	Execution time	Memory
974337		Unforgettablepl	Strange Device (APIO19_strange_device)	C++17	100 / 100	668 ms	102300 KiB

strange_device

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

#define int long long

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,A,B;
    cin >> n >> A >> B;
    __int128 modulus = __int128(A/gcd(A,B+1))*__int128(B);
    set<__int128> answers;
    vector<pair<__int128,bool>> events;
    for(int i=1;i<=n;i++){
        int tl,tr;cin>>tl>>tr;__int128 l = tl,r=tr;
        __int128 block_l = l/modulus;
        __int128 block_r = r/modulus;
        l%=modulus;
        r%=modulus;
        if(block_l == block_r){
            events.emplace_back(l,false);
            events.emplace_back(r+1,true);
        } else if(block_l+1 == block_r){
            events.emplace_back(l,false);
            events.emplace_back(r+1,true);
            events.emplace_back(0,false);
            events.emplace_back(modulus,true);
        } else {
            cout << (int)modulus << '\n';
            return 0;
        }
    }
    sort(events.begin(), events.end());
    __int128 last = -1;
    int curractive = 0;
    __int128 currans = 0;
    for(auto[idx,type]:events){
        if(type){
            if(--curractive==0){
                currans+=idx-last;
            }
        } else{
            if(curractive++==0){
                last = idx;
            }
        }
    }
    cout << (int)currans << '\n';
}

• 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