Submission #1136813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136813		imarn	Inspections (NOI23_inspections)	C++20	55 / 100	527 ms	35964 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=2e5+5,inf=1e9+7;
vector<pii>g[mxn];
multiset<pii>ms[2];
ll s[mxn];
ll fw[mxn]{0};
void add(int i,ll amt){
    for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
ll qr(int i,ll rs=0){
    for(;i;i-=i&-i)rs+=fw[i];
    return rs;
}
vector<ll>v;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;ll sum=0;
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        g[l].pb({i,sum-l+1});
        g[r+1].pb({-i,sum-l+1});
        sum+=r-l+1;
    }for(int i=1;i<=q;i++)cin>>s[i],s[i]++,v.pb(s[i]);sort(all(v));v.erase(unique(all(v)),v.end());
    for(int j=1;j<=n;j++){
        for(auto [i,w] : g[j]){
            if(i>0){
                ms[0].insert({i,w});
                auto it=ms[0].lower_bound({i,w});
                if(it!=ms[0].begin()&&it!=(--ms[0].end())){
                    it--;auto il=it;it++;
                    it++;auto ir=it;it--;ll x=ir->s-il->s;
                    ms[1].erase({il->f,x});
                    add(1,-(n-j+1));
                    add(ub(v,x)+1,n-j+1);
                }
                if(it!=ms[0].begin()){
                    it--;auto ij=it;it++;ll x=it->s-ij->s;
                    ms[1].insert({ij->f,x});
                    add(1,n-j+1);
                    add(ub(v,x)+1,-(n-j+1));
                }
                if(it!=(--ms[0].end())){
                    it++;auto ij=it;it--;ll x=ij->s-it->s;
                    ms[1].insert({it->f,x});
                    add(1,n-j+1);
                    add(ub(v,x)+1,-(n-j+1));
                }
            }
            else {
                i=-i;
                auto it=ms[0].lower_bound({i,w});
                if(it!=ms[0].begin()&&it!=(--ms[0].end())){
                    it--;auto il=it;it++;
                    it++;auto ir=it;it--;ll x=ir->s-il->s;
                    ms[1].insert({il->f,x});
                    add(1,(n-j+1));
                    add(ub(v,x)+1,-(n-j+1));
                }
                if(it!=ms[0].begin()){
                    it--;auto ij=it;it++;ll x=it->s-ij->s;
                    ms[1].erase({ij->f,x});
                    add(1,-(n-j+1));
                    add(ub(v,x)+1,(n-j+1));
                }
                if(it!=(--ms[0].end())){
                    it++;auto ij=it;it--;ll x=ij->s-it->s;
                    ms[1].erase({it->f,x});
                    add(1,-(n-j+1));
                    add(ub(v,x)+1,(n-j+1));
                }ms[0].erase({i,w});
            }
        }
    }for(int i=1;i<=q;i++)cout<<qr(ub(v,s[i]))<<' ';
}

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