Submission #635813

#	Time	Username	Problem	Language	Result	Execution time	Memory
635813		PoonYaPat	Strange Device (APIO19_strange_device)	C++14	0 / 100	8 ms	2108 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll n,A,B,mod,ans;
set<pll> s; //(end,start)

void insert(pll a) {
    if (s.empty()) {
        s.insert(a);
        ans+=(a.second-a.first+1);
    } else {
        auto it1=s.upper_bound(pll(a.first,LLONG_MAX));
        auto it2=s.upper_bound(pll(a.second,LLONG_MAX));
        ll mmin, mmax;
        auto ed=it1,st=it1;

        if (it1==s.begin()) mmin=a.first;
        else {
            auto h=it1; --h;
            if ((*h).second>=a.first) mmin=(*h).first,st=h;
            else mmin=a.first,st=it1;
        }

        ed=it2;
        if (it2==s.begin()) mmax=a.second;
        else {
            --it2;
            mmax=max(a.second,(*it2).second);
        }

        for (auto k=st; k!=ed; ++k) {
            ans-=((*k).second-(*k).first+1);
            auto p=k; s.erase(p);
        }

        s.insert(pll(mmin,mmax));
        ans+=(mmax-mmin+1);

        //cout<<ans<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>A>>B;

    mod=(A*B)/__gcd(A,B+1);

    while (n--) {
        ll l,r;
        cin>>l>>r;
        if (r-l+1>=mod) {
            cout<<mod;
            return 0;
        }
        l%=mod;
        r%=mod;

        if (l<=r) insert(pll(l,r));
        else insert(pll(l,mod-1)), insert(pll(0,r));
    }

    cout<<ans;
}
/*
2 3 3
7 9
17 18
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30