Submission #921166

#	Time	Username	Problem	Language	Result	Execution time	Memory
921166		MtSaka	Inspections (NOI23_inspections)	C++17	0 / 100	0 ms	348 KiB

Main

#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++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(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
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);}
static constexpr ll mod1=998244353;
static constexpr ll mod=1000000007;
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,m,q;cin>>n>>m>>q;
    vl l(m),r(m);
    rep(i,m)cin>>l[i]>>r[i];
    for(auto&e:l)e--;
    vl s(q);
    for(auto&e:s)cin>>e;
    vl idx(q);iota(all(idx),0);
    sort(all(idx),[&](ll i,ll j){return s[i]>s[j];});
    map<ll,ll>cnt;
    set<tuple<ll,ll,ll>>st;
    st.insert({0,n,-1});
    ll now=0;
    rep(i,m){
        //for(auto [i,j,k]:st)cerr<<i<<" "<<j<<" "<<k<<endl;
        //cerr<<endl;
        ll tmp=l[i];
        auto it=st.lower_bound({l[i],-1,-1});
        if(it!=st.begin()){
            auto pit=prev(it);
            auto prev=*pit;
            if(get<1>(prev)>l[i]){
                ll lt=get<2>(prev);
                if(get<1>(prev)<=r[i]){
                    if(lt!=-1){
                        lt+=l[i]-get<0>(prev);
                        cnt[now-lt]+=get<1>(prev)-l[i];
                    }
                    now+=get<1>(prev)-l[i];
                    st.erase(pit);
                    st.insert({get<0>(prev),l[i],get<2>(prev)});
                    tmp=get<1>(prev);
                }
                else{
                    if(lt!=-1){
                        lt+=l[i]-get<0>(prev);
                        cnt[now-lt]+=r[i]-l[i];
                    }
                    now+=r[i]-l[i];
                    st.erase(pit);
                    st.insert({get<0>(prev),l[i],get<2>(prev)});
                    st.insert({r[i],get<1>(prev),get<2>(prev)+r[i]-get<0>(prev)});
                    tmp=r[i];
                }
            }
        }
        while(tmp<r[i]&&it!=st.end()){
            auto prev=*it;
            if(get<0>(prev)>=r[i])break;
            assert(get<0>(prev)==tmp);
            if(get<1>(prev)<=r[i]){
                it=st.erase(it);
                if(get<2>(prev)!=-1)cnt[now-get<2>(prev)]+=get<1>(prev)-get<0>(prev);
                tmp=get<1>(prev);
                now+=get<1>(prev)-get<0>(prev);
            }
            else{
                it=st.erase(it);
                if(get<2>(prev)!=-1)cnt[now-get<2>(prev)]+=r[i]-get<0>(prev);
                tmp=r[i];
                now+=r[i]-get<0>(prev);
                st.insert({r[i],get<1>(prev),get<2>(prev)+r[i]-get<0>(prev)});
            }
        }
        assert(tmp==r[i]);
        st.insert({l[i],r[i],now-(r[i]-l[i])});
        //cerr<<now<<endl;
    }
    ll sum=0;
    vl ans(q);
    for(auto id:idx){
        while(cnt.size()&&(prev(cnt.end())->first)>s[id]){
            sum+=prev(cnt.end())->second;
            cnt.erase(prev(cnt.end()));
        }
        ans[id]=sum;
    }
    rep(i,q){
        cout<<ans[i]<<" ";
    }
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 23