Submission #1272616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272616		minhpk	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	509 ms	63336 KiB

matryoshka

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,c;
pair<int,int> z[1000005];
vector <int> v;
vector <int> v1;
vector <int> pos[1000005];
vector <pair<int,int>> pos1[1000005];
pair<int,int> q[1000005];
pair<int,int> f[4000005];
int inf=1e16;
int res[1000005];
void build(int id,int l,int r){
    if (l==r){
        f[id]={inf,0};
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    f[id].first=min(f[id*2].first,f[id*2+1].first);
    f[id].second=f[id*2].second+f[id*2+1].second;
}
void update(int id,int l,int r,int pos,int val){
    if (l==r){
        f[id].second+=val;
        if (f[id].second==1){
             f[id].first=l;
        }
        if (f[id].second==0){
             f[id].first=inf;
        }
        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].first=min(f[id*2].first,f[id*2+1].first);
    f[id].second=f[id*2].second+f[id*2+1].second;
}
int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return inf;
    }
    if (l>=x && y>=r){
        return f[id].first;
    }
    int mid=(l+r)/2;
    return min(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}
int get1(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        return f[id].second;
    }
    int mid=(l+r)/2;
    return get1(id*2,l,mid,x,y)+get1(id*2+1,mid+1,r,x,y);
}
signed main()
{
    if (fopen("bb.inp","r")){
        freopen("bb.inp","r",stdin);
        freopen("bb.out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> c;   
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
         v.push_back(z[i].first);
         v1.push_back(z[i].second);
    }
    
    for (int i=1;i<=c;i++){
         cin >> q[i].first >> q[i].second;
         v.push_back(q[i].first);
         v1.push_back(q[i].second);
    }
    sort(v.begin(),v.end());
    sort(v1.begin(),v1.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    v1.erase(unique(v1.begin(),v1.end()),v1.end());

    for (int i=1;i<=a;i++){
         z[i].first=lower_bound(v.begin(),v.end(),z[i].first)-v.begin()+1;
         z[i].second=lower_bound(v1.begin(),v1.end(),z[i].second)-v1.begin()+1;
         pos[z[i].first].push_back(z[i].second);
    }
    for (int i=1;i<=c;i++){
         q[i].first=lower_bound(v.begin(),v.end(),q[i].first)-v.begin()+1;
         q[i].second=lower_bound(v1.begin(),v1.end(),q[i].second)-v1.begin()+1;
         pos1[q[i].first].push_back({q[i].second,i});
    }
    int n=v.size();
    int n1=v1.size();
    build(1,1,n1);
    for (int i=n;i>=1;i--){
         vector <int> add;
         for (auto p:pos[i]){
              int val=get(1,1,n1,p+1,n1);
              add.push_back(p);
              if (val!=inf){
                  update(1,1,n1,val,-1);
              }
         }
         for (auto p:add){
              update(1,1,n1,p,1);
         }
         for (auto p:pos1[i]){
              res[p.second]=get1(1,1,n1,1,p.first);
         }
    }
    for (int i=1;i<=c;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("bb.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("bb.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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