Submission #1232341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232341		Warinchai	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	355 ms	45652 KiB

matryoshka

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fw{
    int info[400005];
    void upd(int id,int val){
        for(int i=id;i<=4e5;i+=i&-i)info[i]+=val;
    }
    int fans(int id){
        int ans=0;
        for(int i=id;i>0;i-=i&-i)ans+=info[i];
        return ans;
    }
}all,ans;
int rans[200005];
vector<pair<int,pair<int,int>>>op[400005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    vector<int>val;
    vector<int>valy;
    vector<pair<int,int>>doll;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        val.push_back(x);
        doll.push_back({x,y});
        valy.push_back(y);
    }
    vector<pair<int,int>>qr;
    for(int i=0;i<q;i++){
        int x,y;cin>>x>>y;
        qr.push_back({x,y});
        val.push_back(x);
        valy.push_back(y);
    }
    //cerr<<"work\n";
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    sort(valy.begin(),valy.end());
    valy.erase(unique(valy.begin(),valy.end()),valy.end());
    //cerr<<"work\n";
    for(auto x:doll){
        x.first=lower_bound(val.begin(),val.end(),x.first)-val.begin()+1;
        x.second=lower_bound(valy.begin(),valy.end(),x.second)-valy.begin()+1;
        op[x.first].push_back({1,{x.second,0}});
    }
    for(int i=0;i<qr.size();i++){
        auto x=qr[i];
        x.first=lower_bound(val.begin(),val.end(),x.first)-val.begin()+1;
        x.second=lower_bound(valy.begin(),valy.end(),x.second)-valy.begin()+1;
        op[x.first].push_back({0,{x.second,i}});
    }
    for(int i=1;i<=val.size();i++){
        sort(op[i].begin(),op[i].end());
    }
    multiset<int>ms;
    //cerr<<"work\n";
    for(int i=val.size();i>=1;i--){
        vector<int>upd;
        vector<int>add;
        for(auto temp:op[i]){
            int t=temp.first;
            int y=temp.second.first;
            int id=temp.second.second;
            if(t==1){
                auto p=ms.upper_bound(y);
                if(p!=ms.end()){
                    int pp=*p;
                    ms.erase(p);
                    upd.push_back(pp);
                }
                add.push_back(y);
                all.upd(y,1);
            }
        }
        for(auto x:add)ms.insert(x);
        for(auto x:upd)ans.upd(x,1);
        for(auto temp:op[i]){
            int t=temp.first;
            int y=temp.second.first;
            int id=temp.second.second;
            if(t==0){
                rans[id]=all.fans(y)-ans.fans(y);
            }
        }
    }
    for(int i=0;i<q;i++)cout<<rans[i]<<"\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49