Submission #1273409

#TimeUsernameProblemLanguageResultExecution timeMemory
1273409nthvnExamination (JOI19_examination)C++20
100 / 100
236 ms10124 KiB
#include "bits/stdc++.h"
using namespace std;
#define cerr if(0) cerr
#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N = 2e5+5;
int n,q,tot, fans[N];
struct DATA{
    int x,y,z,id;
    bool operator < (const DATA &o ) const{
        if(x==o.x) return id< o.id;
        return x> o.x;
    }
    void print(){
        cerr<<x<<" "<<y<<" "<<z<<"\n";
    }
} a[N], t[N];
struct BITREV{
    int bit[N];
    void update(int i, int x){
        for(;i;i-=i&-i) bit[i]+=x;
    }
    int get(int i){
        int ans =0;
        for(;i<=tot;i+=i&-i) ans+= bit[i];
        return ans;
    }
}bit;

void compress(){
    vector<int> X,Y,Z;
    for(int i=1;i<=tot;i++) {
        X.pb(a[i].x), Y.pb(a[i].y), Z.pb(a[i].z);
    }
    sort(all(X));
    sort(all(Y));
    sort(all(Z));
    for(int i=1;i<=tot;i++){
        a[i].x = lower_bound(all(X), a[i].x) - X.begin()+1;
        a[i].y = lower_bound(all(Y), a[i].y) - Y.begin()+1;
        a[i].z = lower_bound(all(Z), a[i].z) - Z.begin()+1;
    }
}

vector<pii> hist;
void mg(int x, int y, int u, int v){
    
    int st= x-1;
    int L= x, R=u;
    
    while(L<=y&&R<=v){
        if(a[L].y>= a[R].y){
            t[++st] = a[L];
            int z= a[L].z;
            if(!a[L].id){
                hist.pb({z,-1});
                bit.update(z,1);
            }
            L++;
        }
        else{
            t[++st] = a[R];
            int z= a[R].z;
            if(a[R].id) fans[a[R].id] += bit.get(z);
            R++;
        }
    }
    while(L<=y){
        t[++st]= a[L++];
    }
    while(R<=v){
        if(a[R].id) fans[a[R].id] += bit.get(a[R].z);
        t[++st]= a[R++];
    }
    cerr<<x<<" "<<y<<" "<<u<<" "<<v<<" "<<L<<" "<<R<<"\n";
    for(int i=x;i<=v;i++) a[i].print();
    cerr<<"__________________\n";
    for(int i=x;i<=v;i++) t[i].print();
    cerr<<"\n\n";
    
    for(int i=x;i<=v;i++) a[i] = t[i];
    while(sz(hist)){
        bit.update(hist.back().fi, hist.back().se);
        hist.pop_back();
    }
}

void dnc(int l, int r){
    if(l==r) return;
    int mid =(l+r)>>1;
    dnc(l,mid);
    dnc(mid+1,r);
    mg(l,mid, mid+1,r);
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    if(fopen("TASK.INP", "r")){
        freopen("TASK.INP", "r", stdin);
        freopen("TASK.OUT", "w", stdout);
    }
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x,y; cin>>x>>y;
        a[++tot] = {x,y,x+y,0};
    }
    for(int i=1;i<=q;i++){
        int x,y,z; cin>>x>>y>>z;
        a[++tot] = {x,y,z,i};
    }
    compress();
    cerr<<"A\n";
    for(int i=1;i<=n;i++) a[i].print();
    cerr<<"\nB\n";
    for(int i=n+1;i<=tot;i++) a[i].print();
    sort(a+1,a+tot+1);
    
    cerr<<"\nT\n";
    for(int i=1;i<=tot;i++) a[i].print();
    cerr<<"\n\n";
    
    dnc(1,tot);
    
    for(int i=1;i<=q;i++) cout<<fans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("TASK.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("TASK.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...