Submission #1162644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162644		Otalp	Strange Device (APIO19_strange_device)	C++20	100 / 100	617 ms	78740 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map
#define dll __int128

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;



void solve(){
    int n = 50;
    cin>>n;
    ll A, B;
    cin>>A>>B;
    dll a = A, b = B;
    dll d = a * b / __gcd(a , b + 1);
    ll ans = 0;
    map<dll, dll> q;
    for(int i=1; i<=n; i++){
        ll l, r;
        cin>>l>>r;
        if(ans == d) continue;
        if(r - l + 1 >= d){
            ans = d;
        }
        else{
            if(l % d <= r % d){
                q[r % d + 1] -= 1;
                q[l % d] += 1;
            }
            else{
                q[0] += 1;
                q[r % d + 1] -= 1;
                q[l % d] += 1;
                q[d] -= 1;
            }
        }
    }
    if(ans == d){
        cout<<ans;
        return;
    }
    dll ls = -1;
    dll x = 0;
    for(auto g: q){
        ans += bool(x > 0) * (g.ff - ls);
        x += g.ss;
        ls = g.ff;
    }
    cout<<ans; 
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\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