제출 #729959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729959		MtSaka	이상한 기계 (APIO19_strange_device)	C++17	0 / 100	1 ms	320 KiB

strange_device

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)a;++i)
#define rep3(i,a,b) for(ll i=a;i<(ll)b;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define lb(v,x) lower_bound(all(v),x);
#define ub(v,x) upper_bound(all(v),x);
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
struct segmnet_set{
    private:
    set<pair<ll,ll>>st;
    public:
    segmnet_set(){}
    void add(ll l,ll r){
        if(st.empty()){
            st.insert({l,r});
            return;
        }
        auto it=st.lower_bound({l,-1});
        if(it!=st.begin()){
            if(prev(it)->second>=l){
                l=prev(it)->first;
                chmax(r,prev(it)->second);
                st.erase(prev(it));
            }
        }
        while(it!=st.end()&&it->first<=r){
            chmax(r,it->second);
            it++;
            st.erase(prev(it));
        }
        st.insert({l,r});
    }
    ll calc()const{
        ll ans=0;
        for(const auto&[l,r]:st)ans+=r-l;
        return ans;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    ll a,b;cin>>a>>b;
    ll g=gcd(a,b+1);
    if((100000000000000000+b-1)/b<a/g){
        ll ans=0;
        rep(i,n){
            ll l,r;cin>>l>>r;ans+=r-l+1;
        }
        cout<<ans<<endl;return 0;
    }
    segmnet_set st;
    ll md=a/g*b;
    rep(i,n){
        ll l,r;cin>>l>>r;
        r++;
        l%=md,r%=md;
        if(l>r){
            st.add(l,md),st.add(0,r);
        }
        else{
            st.add(l,r);
        }
    }
    cout<<st.calc()<<endl;
}

• 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