Submission #1369863

#TimeUsernameProblemLanguageResultExecution timeMemory
1369863vuacualoaiboExamination (JOI19_examination)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define iloveclc  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define MOD 1000000007
#define all(a) a.begin(),a.end()
using namespace std;

#define solve_problem namespace

const int MAXN=6e5+1;
struct po{

    int x,y,z,i;

    bool operator < (const po& other)const{

         if(x!=other.x)return x>other.x;
         else return y>other.y;

    }

};


int n,q,cnt=0,len;int res[MAXN];
po a[MAXN];ii b[MAXN];
int st[4*MAXN];


void update(int id,int u,int l,int r,int val){



     if(l==r){
         st[id]+=val;
         return;
     }

     int mid=(l+r)/2;
     if(mid>=u)update(id*2,u,l,mid,val);
     else update(id*2+1,u,mid+1,r,val);
     st[id]=st[id*2]+st[id*2+1];

}

int get(int id,int u,int v,int l,int r){

     if(l>v||r<u)return 0;

     if(l>=u&&r<=v)return st[id];

     int mid=(l+r)/2;
     return get(id*2,u,v,l,mid)+get(id*2+1,u,v,mid+1,r);

}

void dln(int l,int r){

     int m=(l+r)/2;
     //cout<<l<<" "<<r<<endl;
     if(l==r)return;
     dln(l,m);dln(m+1,r);

     vector<po>get_back;
     vector<int>kl;

     l=b[l].first;
     m=b[m].second;
     r=b[r].second;



     int j=l,j1=m+1;

     while(j<m+1&&j1<r+1){


        if(a[j].y>a[j1].y){

            if(a[j].i==0)update(1,a[j].z,1,len,1);

            get_back.push_back(a[j]);
            if(a[j].i==0)kl.push_back(a[j].z);
            j++;

        }
        else{

            if(a[j1].i!=0)res[a[j1].i]+=get(1,a[j1].z+1,len,1,len);

            get_back.push_back(a[j1]);
            j1++;

        }

     }


    while(j<m+1)
    {

        if(a[j].i==0)update(1,a[j].z,1,len,1);
        get_back.push_back(a[j]);
        if(a[j].i==0)kl.push_back(a[j].z);
        j++;

    }

    while(j1<r+1)
    {

        if(a[j1].i!=0)res[a[j1].i]+=get(1,a[j1].z+1,len,1,len);
        get_back.push_back(a[j1]);
        j1++;

    }

    fr(i,l,r)
      a[i]=get_back[i-l];

    for(int v:kl)
        update(1,v,1,len,-1);


}

int main() {

    iloveclc;

    freopen("ANHDEP.inp","r",stdin);
freopen("ANHDEP.out","w",stdout);

    cin>>n>>q;
    vector<int>c;



    fr(i,1,n){

       cin>>a[i].x;cin>>a[i].y;a[i].z=a[i].x+a[i].y;
       a[i].i=0;
       c.push_back(a[i].x);
       c.push_back(a[i].y);
       c.push_back(a[i].z);

    }

    fr(i,1,q){

        cin>>a[i+n].x;cin>>a[i+n].y;cin>>a[i+n].z;
        a[i+n].x--;
        a[i+n].y--;
        a[i+n].z--;
         a[i+n].i=i;
       c.push_back(a[i+n].x);
       c.push_back(a[i+n].y);
       c.push_back(a[i+n].z);
    }

    n+=q;

    sort(all(c));
    c.erase(unique(all(c)),c.end());



    fr(i,1,n){

       a[i].x=lower_bound(all(c),a[i].x)-c.begin()+1;
       a[i].y=lower_bound(all(c),a[i].y)-c.begin()+1;
       a[i].z=lower_bound(all(c),a[i].z)-c.begin()+1;

    }

    sort(a+1,a+n+1);
    len=c.size();

    int l=1;

    fr(i,2,n)
        if(a[i].x!=a[i-1].x){
            cnt++;
            b[cnt]={l,i-1};
            l=i;
        }

    cnt++;
    b[cnt]={l,n};



    dln(1,cnt);

    int ans=0;

    fr(i,1,q)
       cout<<res[i]<<endl;;

     //cout<<ans;

    #define i_love_chi_linh_chi_so_much return
    #define _5000_ 0
    i_love_chi_linh_chi_so_much _5000_;

}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen("ANHDEP.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:137:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 | freopen("ANHDEP.out","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...