Submission #167199

#	Time	Username	Problem	Language	Result	Execution time	Memory
167199		jh05013	Examination (JOI19_examination)	C++17	2 / 100	3102 ms	279224 KiB

examination

#include <bits/stdc++.h>
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}

template <typename T>
struct Compress{
    int n; vector<T> arr;
    void add(T x){arr.push_back(x); n++;}
    void init(){sort(entire(arr)), arr.erase(unique(entire(arr)), arr.end());}
    int lb(T x){return lower_bound(entire(arr), x) - arr.begin();}
    int ub(T x){return upper_bound(entire(arr), x) - arr.begin();}
};

template <typename T>
struct Fenwick2d{
    int n, m;
    vector<unordered_map<int, T>> arr;
    Fenwick2d(int N, int M): n(N), m(M), arr(n) {}
    void update(int i, int j, T val){
        for(; i<n; i|=i+1) for(int p=j; p<m; p|=p+1) 
            arr[i][p]+= val;
    }
    T getsum(int i, int j){
        T res = 0;
        for(; i>=0; i=(i&(i+1))-1) for(int p=j; p>0; p=(p&(p+1))-1)
            res+= arr[i][p];
        return res;
    }
};

int main(){OJize();
    int n, q; cin>>n>>q;
    Compress<int> CX, CY;
    vector<tuple<int,int,int>> stu;
    vector<tuple<int,int,int,int>> query;
    for(int i=0; i<n; i++){
        int x,y; cin>>x>>y;
        stu.push_back({-x-y,x,y});
        CX.add(x), CY.add(y);
    }
    CX.init(), CY.init();
    sort(entire(stu));
    for(int i=0; i<q; i++){
        int x,y,z; cin>>x>>y>>z;
        query.push_back({-z,CX.lb(x),CY.lb(y),i});
    }
    sort(entire(query));

    vector<int> ans(q);
    Fenwick2d<int> F(n+2, n+2);
    int ptr = 0;
    for(auto [mz,x,y,i]: query){
        while(ptr<n){
            auto [mxyp, xp, yp] = stu[ptr];
            if(mxyp > mz) break;
            F.update(n-CX.lb(xp), n-CY.lb(yp), 1);
            ptr++;
        }
        ans[i] = F.getsum(n-x, n-y);
    }
    for(int x: ans) cout<<x<<'\n';
}

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