Submission #1271688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271688		letienbinh_812	Examination (JOI19_examination)	C++20	100 / 100	403 ms	24132 KiB

examination

#include<bits/stdc++.h>
#define N 1000000
#define inf int(1e9+7)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<long long, int> li;
typedef pair<long long, li> loli;
// loli
loli gspvhcute;
//:333


const int M = 1e9+7;
int n,m;
pair<int,int> a[N+3];
pair<pair<int,int>,pair<int,int>> b[N+3];
vector<int> dsx, dsy;
int ans[N+3];

struct BIT1D {
    vector<long long> bit;
    BIT1D() {}
    BIT1D(int n) : bit(n + 1, 0) {}
    void add(int i, long long v) {
        for (; i < (int)bit.size(); i += i & -i) bit[i] += v;
    }
    long long sum(int i) const {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
};

struct Fenwick2D {
    int nx;
    vector<vector<int>> ys;
    vector<BIT1D> bit;

    Fenwick2D(int nx) : nx(nx), ys(nx + 1), bit(nx + 1) {}

    void collect_point(int x, int y) {
        for (int i = x; i <= nx; i += i & -i)
            ys[i].push_back(y);
    }

    void build() {
        for (int i = 1; i <= nx; i++) {
            sort(ys[i].begin(), ys[i].end());
            ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
            bit[i] = BIT1D((int)ys[i].size());
        }
    }


    void update(int x, int y, long long v) {
        for (int i = x; i <= nx; i += i & -i) {
            int iy = int(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin()) + 1;
            bit[i].add(iy, v);
        }
    }


    long long query(int x, int y) const {
        long long res = 0;
        for (int i = x; i > 0; i -= i & -i) {
            int iy = int(upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
            if (iy > 0) res += bit[i].sum(iy);
        }
        return res;
    }

    long long rect(int x1, int y1, int x2, int y2) const {
        return query(x2, y2)
             - query(x1 - 1, y2)
             - query(x2, y1 - 1)
             + query(x1 - 1, y1 - 1);
    }
};



void Solve(){
    auto getX = [&](long long v){
        return int(lower_bound(dsx.begin(), dsx.end(), v) - dsx.begin()) + 1;
    };
    auto getY = [&](long long v){
        return int(lower_bound(dsy.begin(), dsy.end(), v) - dsy.begin()) + 1;
    };

    Fenwick2D fw(dsx.size());

    for (int i=1; i<=n; i++) {
        int cx = getX(a[i].first);
        int cy = getY(a[i].second);
        fw.collect_point(cx, cy);
    }
    fw.build();


    int j = 1;
    for(int i=1; i<=m; i++){
        while(j <= n && a[j].first + a[j].second >= b[i].first.first){
            fw.update(getX(a[j].first), getY(a[j].second),1);
            j++;
        }
        ans[b[i].first.second] = fw.rect(getX(b[i].second.first), getY(b[i].second.second),
                                         getX(dsx.back()), getY(dsy.back()));
    }
    for(int i=1; i<=m; i++) cout << ans[i] << "\n";

}

void Inp(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i].first >> a[i].second;
    for(int i=1; i<=m; i++) cin >> b[i].second.first >> b[i].second.second >> b[i].first.first, b[i].first.second = i;
    sort(a+1,a+n+1, [&](pair<int,int> X, pair<int,int> Y){
         return X.first + X.second > Y.first + Y.second;
    });
    sort(b+1,b+m+1, greater<pair<pair<int,int>,pair<int,int>>>());

    for(int i=1; i<=n; i++) dsx.push_back(a[i].first), dsy.push_back(a[i].second);
    sort(all(dsx));
    sort(all(dsy));
    dsx.erase(unique(all(dsx)),dsx.end());
    dsy.erase(unique(all(dsy)),dsy.end());
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
     
    int T=1;
//    cin >> T;
    while(T--){
    Inp();
    Solve();
    }
}
//-----YEU CRUSH HON CODE-----//

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