Submission #702495

#	Time	Username	Problem	Language	Result	Execution time	Memory
702495		alvingogo	Examination (JOI19_examination)	C++14	0 / 100	3099 ms	34676 KiB

examination

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct BIT{
    int n;
    vector<int> bt;
    void init(int x){
        n=x;
        bt.resize(x+1);
    }
    void update(int x,int y){
        x++;
        for(;x<=n;x+=(x&-x)){
            bt[x]+=y;
        }
    }
    int query(int x){
        x++;
        int ans=0;
        for(;x>0;x-=(x&-x)){
            ans+=bt[x];
        }
        return ans;
    }
}bt;
vector<int> g;
struct no{
    int x,y,z;
    int id;
    no(int a,int b,int c,int d){
        x=a;
        y=b;
        z=c;
        id=d;
    }
};
vector<no> v;
vector<int> ans;
void add(int a,int b,int c,int d){
    v.push_back({-a,-b,-c,d});
    g.push_back(-c);
}
bool cmp(no a,no b){
    if(a.x==b.x){
        return a.id<b.id;
    }
    return a.x<b.x;
}
bool cmp2(no a,no b){
    if(a.y==b.y){
        return a.id<b.id;
    }
    return a.y<b.y;
}
void dc(int l,int r){
    if(l==r){
        return;
    }
    int m=(l+r)/2;
    dc(l,m);
    dc(m+1,r);
    sort(v.begin()+l,v.begin()+m+1,cmp2);
    sort(v.begin()+m+1,v.begin()+r+1,cmp2);
    int a=l,b=m+1;
    while(a<=m || b<=r){
        cout << a << " " << b << endl;
        if(a>m || (b<=r && !cmp2(v[a],v[b]))){
            if(v[b].id<0){
                b++;
                continue;
            }
            ans[v[b].id]+=bt.query(v[b].z);
            b++;
        }
        else{
            if(v[a].id>=0){
                a++;
                continue;
            }
            bt.update(v[a].z,1);
            a++;
        }
    }
    for(int i=l;i<=m;i++){
        if(v[i].id<0){
            bt.update(v[i].z,-1);
        }
    }
}
int main(){
    AquA;
    int n,q;
    cin >> n >> q;
    bt.init(n+q);
    for(int i=0;i<n;i++){
        int a,b;
        cin >> a >> b;
        int c=a+b;
        add(a,b,c,-1);
    }
    ans.resize(q);
    for(int i=0;i<q;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c,i);
    }
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    sort(v.begin(),v.end(),cmp);
    for(auto &h:v){
        h.z=lower_bound(g.begin(),g.end(),h.z)-g.begin();
        cout << h.z << endl;
    }
    dc(0,n+q-1);
    for(int i=0;i<q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

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