제출 #1252057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252057		minhpk	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	553 ms	103084 KiB

matryoshka

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
pair<int,int> z[1000005];
pair<int,int> q[1000005];
vector<int> v1,v2;
vector <pair<int,int>> pre[1000005];
vector<int> pos[1000005];
struct node{
      int val,min1;
};
node f[4000005];
int sl[1000005];
int bruh=1e16;
node combine(node a,node b){
     node res;
     res.val=a.val+b.val;
     res.min1=min(a.min1,b.min1);
     return res;
}
void update(int id,int l,int r,int pos,int val){
     if (l==r){
         sl[l]+=val;
         f[id].val+=val;
         if (sl[l]==0){
             f[id].min1=bruh;
         }else{
             f[id].min1=l;
         }
         return;
     }
     int mid=(l+r)/2;
     if (pos<=mid){
         update(id*2,l,mid,pos,val);
     }else{
         update(id*2+1,mid+1,r,pos,val);
     }
     f[id]=combine(f[id*2],f[id*2+1]);
}
node get(int id,int l,int r,int x,int y){
     if (x>r || y<l){
         return {0,bruh};
     }
     if (l>=x && y>=r){
         return f[id];
     }
     int mid=(l+r)/2;
     return combine(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}
int res[1000005];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
         v1.push_back(z[i].first);
         v2.push_back(z[i].second);
    }
    for (int i=1;i<=b;i++){
         cin >> q[i].first >> q[i].second;
         v1.push_back(q[i].first);
         v2.push_back(q[i].second);
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    v1.erase(unique(v1.begin(),v1.end()),v1.end());
    v2.erase(unique(v2.begin(),v2.end()),v2.end());
    int n1=v1.size();
    int n2=v2.size();

    for (int i=1;i<=a;i++){
         z[i].first=lower_bound(v1.begin(),v1.end(),z[i].first)-v1.begin()+1;
         z[i].second=lower_bound(v2.begin(),v2.end(),z[i].second)-v2.begin()+1;
         pos[z[i].first].push_back(z[i].second);
    }
    for (int i=1;i<=b;i++){
         q[i].first=lower_bound(v1.begin(),v1.end(),q[i].first)-v1.begin()+1;
         q[i].second=lower_bound(v2.begin(),v2.end(),q[i].second)-v2.begin()+1;
         pre[q[i].first].push_back({q[i].second,i});
    }
    for (int i=1;i<=n2*4;i++){
         f[i]={0,bruh};
    }
    for (int i=n1;i>=1;i--){
         for (auto p:pos[i]){
             int sad=get(1,1,n2,p+1,n2).min1;
             if (sad!=bruh){
                 update(1,1,n2,sad,-1);
             }
         }
         for (auto p:pos[i]){
             update(1,1,n2,p,1);
         }
         for (auto p:pre[i]){
              res[p.second]=get(1,1,n2,1,p.first).val;
         }
    }
    for (int i=1;i<=b;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

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