Submission #1102804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102804		Icelast	Examination (JOI19_examination)	C++17	100 / 100	946 ms	139688 KiB

examination

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct point{
    ll x, y, z, id;
};
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
struct Fenwick2D {
    int n, m;
    vector<vector<int>> bit;
    vector<vector<int>> f;

    Fenwick2D(int n, int m) : n(n), m(m), bit(n + 1), f(n + 1) {}

    void fakeAdd(int i0, int j0) {
        for (int i = i0; i <= n; i += i & -i) {
            for (int j = j0; j <= m; j += j & -j) {
                f[i].push_back(j);
            }
        }
    }

    void work() {
        for (int i = 1; i <= n; i++) {
            f[i].push_back(0);
            sort(f[i].begin(), f[i].end());
            f[i].resize(unique(f[i].begin(), f[i].end()) - f[i].begin());
            bit[i].resize(f[i].size(), 0);
        }
    }

    void add(int i0, int j0, int x) {
        for (int i = i0; i <= n; i += i & -i) {
            for (int j = lower_bound(f[i].begin(), f[i].end(), j0) - f[i].begin(); j < (int)f[i].size(); j += j & -j) {
                bit[i][j] += x;
            }
        }
    }

    int sum(int i0, int j0) {
        int res = 0;
        for (int i = i0; i > 0; i -= i & -i) {
            for (int j = upper_bound(f[i].begin(), f[i].end(), j0) - f[i].begin() - 1; j > 0; j -= j & -j) {
                res += bit[i][j];
            }
        }
        return res;
    }
};
void solve(){
    int n, Q;
    cin >> n >> Q;
    vector<point> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y;
        a[i].z = a[i].x+a[i].y;
    }
    vector<point> q(Q+1);
    for(int i = 1; i <= Q; i++){
        cin >> q[i].x >> q[i].y >> q[i].z;
        q[i].id = i;
    }
    normalize norm;
    for(int i = 1; i <= n; i++){
        norm.add(a[i].x);
        norm.add(a[i].y);
    }
    for(int i = 1; i <= Q; i++){
        norm.add(q[i].x);
        norm.add(q[i].y);
    }
    norm.start();
    int N = norm.pot.size()+1;
    for(int i = 1; i <= n; i++){
        a[i].x = N-norm.encode(a[i].x);
        a[i].y = N-norm.encode(a[i].y);
    }
    for(int i = 1; i <= Q; i++){
        q[i].x = N-norm.encode(q[i].x);
        q[i].y = N-norm.encode(q[i].y);
    }
    Fenwick2D bit(N+1, N+1);
    for(int i = 1; i <= n; i++){
        bit.fakeAdd(a[i].x, a[i].y);
    }
    bit.work();
    sort(a.begin()+1, a.end(), [&](point a, point b){return a.z > b.z;});
    sort(q.begin()+1, q.end(), [&](point a, point b){return a.z > b.z;});
    vector<ll> ans(Q+1);
    int j = 1;
    for(int i = 1; i <= Q; i++){
        while(j <= n && a[j].z >= q[i].z){
            bit.add(a[j].x, a[j].y, 1);
            j++;
        }
        ans[q[i].id] = bit.sum(q[i].x, q[i].y);
    }
    for(int i = 1; i <= Q; i++){
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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