Submission #914405

#	Time	Username	Problem	Language	Result	Execution time	Memory
914405		guagua0407	Examination (JOI19_examination)	C++17	100 / 100	368 ms	11300 KiB

examination

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
    int x,y,z,id;
    bool operator<(const node &a)const{
        if(x!=a.x) return x<a.x;
        if(y!=a.y) return y<a.y;
        if(z!=a.z) return z<a.z;
        return a.id<id;
    }
};

vector<node>vec;
const int mxn=2e5+5;
int ans[mxn];
int bit[mxn];

void update(int pos,int val){
    for(;pos<mxn;pos+=(pos&-pos)){
        bit[pos]+=val;
    }
}

int query(int pos){
    int ans=0;
    for(;pos;pos-=(pos&-pos)){
        ans+=bit[pos];
    }
    return ans;
}

bool comp(node a,node b){
    return a.y<b.y;
}

void go(int l,int r){
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    go(l,mid);
    go(mid+1,r);
    int R=r;
    for(int L=mid;L>=l;L--){
        while(R>mid and vec[R].y>=vec[L].y){
            if(vec[R].id==-1){
                update(vec[R].z,1);
            }
            R--;
        }
        if(vec[L].id!=-1){
            ans[vec[L].id]+=query(mxn-1)-query(vec[L].z-1);
        }
    }
    R++;
    while(R<=r){
        if(vec[R].id==-1){
            update(vec[R].z,-1);
        }
        R++;
    }
    sort(vec.begin()+l,vec.begin()+r+1,comp);
}

int main() {_
    int n,m;
    cin>>n>>m;
    vec.resize(n+m);
    for(int i=0;i<n;i++){
        cin>>vec[i].x>>vec[i].y;
        vec[i].z=vec[i].x+vec[i].y;
        vec[i].id=-1;
    }
    for(int i=n;i<n+m;i++){
        cin>>vec[i].x>>vec[i].y>>vec[i].z;
        vec[i].id=i-n;
    }
    vector<int> zs;
    zs.push_back(-1);
    for(int i=0;i<n+m;i++){
        zs.push_back(vec[i].z);
    }
    sort(all(zs));
    zs.resize(unique(all(zs))-zs.begin());
    for(int i=0;i<n+m;i++){
        vec[i].z=lower_bound(all(zs),vec[i].z)-zs.begin();
    }
    sort(all(vec));
    go(0,n+m-1);
    for(int i=0;i<m;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message (stderr)

examination.cpp: In function 'void setIO(std::string)':
examination.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57