Submission #1116709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116709		Warinchai	Inspections (NOI23_inspections)	C++14	100 / 100	308 ms	39604 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct range{
    int l,r,val;
    range(int _l=0,int _r=0,int _val=0){
        l=_l,r=_r,val=_val;
    }
    friend bool operator<(range a,range b){
        return a.l<b.l;
    }
};
multiset<range>ms;
vector<pair<int,int>>v;
priority_queue<pair<int,int>>pq;
vector<range>pb;
int lz=0;
int add(range x,range cur){
    if(x.l>cur.r)return 0;
    //cerr<<x.l<<" "<<x.r<<" "<<x.val<<":"<<x.r<<"-"<<cur.l<<"+"<<lz<<"+"<<x.val<<","<<min(x.r,cur.r)-max(x.l,cur.l)+1<<"\n";
    pq.push({x.r-cur.l+lz+x.val,min(x.r,cur.r)-max(x.l,cur.l)+1});
    return 1;
}
int rans[200005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int l,r;cin>>l>>r;
        v.push_back({l,r});
    }
    for(auto [l,r]:v){
        //cerr<<"range:"<<l<<" "<<r<<":\n";
        if(!ms.empty()){
            auto x=ms.lower_bound(range(l));
            if(x!=ms.begin()){
                x=prev(x);
                if(x->r>=l)ms.insert(range(x->l,l-1,x->val+(x->r-l+1))),ms.insert(range(l,x->r,x->val)),ms.erase(x);
            }
            x=ms.upper_bound(range(r));
            if(x!=ms.begin()){
                x=prev(x);
                if(x->r>r)ms.insert(range(x->l,r,x->val+x->r-r)),ms.insert(range(r+1,x->r,x->val)),ms.erase(x);
            }
            x=ms.lower_bound(range(l));
            while(x!=ms.end()&&add(*x,range(l,r))){
                x=next(x);
                ms.erase(prev(x));
            }
        }
        lz+=r-l+1;
        ms.insert(range(l,r,-lz));
    }
    //cerr<<"work\n";
    vector<pair<int,int>>qr;
    for(int i=0;i<q;i++){
        int s;cin>>s;
        qr.push_back({s,i});
    }
    sort(qr.begin(),qr.end(),greater<pair<int,int>>());
    int ans=0;
    for(auto x:qr){
        while(!pq.empty()&&pq.top().first>=x.first){
            //cerr<<pq.top().first<<" "<<pq.top().second<<"\n";
            ans+=pq.top().second,pq.pop();
        }
        //cerr<<"\n";
        rans[x.second]=ans;
    }
    for(int i=0;i<q;i++)cout<<rans[i]<<" ";
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto [l,r]:v){
      |              ^

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