Submission #1361937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361937		MunkhturErdenebat	Strange Device (APIO19_strange_device)	C++20	100 / 100	753 ms	16084 KiB

strange_device

#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <iterator>
#include <set>
#include <stdlib.h>
 #define ll long long
 #define fr first
 #define sc second
 #define pb push_back
 #define YES cout<<"YES"<<endl
 #define NO cout<<"NO"<<endl
 #define endl "\n"
using namespace std;
    ll a,b,c,d,e,f,i,j,n,h,g,mid,l,r,ka,dp[200005],q[200005],m;
    map<ll,ll> mee,see;
    map<ll,ll> mii,maa;
    vector<ll> vas[20005],ves;
    string x,y,z,te,to;
    pair<ll,ll> wefe,k[2000105],t[205005];
    stack<ll> munkh;
    multiset<ll> mul;
int main(){
    cin>>n>>a>>b;
    for(i=1 ; i<=n ; i++){
        cin>>k[i].fr>>k[i].sc;
    }
    g=(a/(gcd(a,(b+1))));
    g*=b;
    m=0;
    for(i=1 ; i<=n ; i++){
        if(k[i].sc-k[i].fr>=g){
            m=g;
            break;
        }
        else{
            k[i].fr%=g;
            k[i].sc%=g;
            if(k[i].sc<k[i].fr){
                k[n+1].fr=0;
                k[n+1].sc=k[i].sc;
                k[i].sc=g-1;
                n++;
            }
        }
    }
    sort(k+1,k+1+n);
    
    if(m>0){
        cout<<g<<endl;
        return 0;
    }
    l=k[1].fr;
    r=k[1].sc;
    ll ans=0;
    for(i=2 ; i<=n ; i++){
        if(k[i].fr>r){
            ans+=r-l+1;
            l=k[i].fr;
            r=k[i].sc;
        }
        else{
            r=max(r,k[i].sc);
        }
    }
    ans+=r-l+1;
    cout<<ans<<endl;
}

• 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