Submission #1345881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345881		khanhphucscratch	Strange Device (APIO19_strange_device)	C++20	100 / 100	525 ms	63076 KiB

strange_device

#include<bits/stdc++.h>
#define int long long
#define intt __int128
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, A, B; cin>>n>>A>>B;
    intt cycle = (intt)A / __gcd(A, B+1) * B;
    //cerr<<"A"<<(int)cycle<<endl;
    map<int, int> f;
    for(int i = 1; i <= n; i++){
        int l, r; cin>>l>>r;
        if(l/cycle + 1 < r / cycle){
            cout<<(int)cycle; return 0;
        }
        else if(l/cycle == r/cycle){
            l %= cycle; r %= cycle;
            f[l]++; f[r+1]--;
        }
        else{
            l %= cycle; r %= cycle;
            f[l]++; f[cycle]--; f[0]++; f[r+1]--;
        }
    }
    int ans = 0, sum = 0, last = -1;
    for(pair<int, int> i : f){
        if(sum > 0) ans += i.first - last;
        //cerr<<"A"<<sum<<" "<<i.first<<" "<<ans<<endl;
        last = i.first; sum += i.second;
    }
    cout<<ans;
}

• 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