Submission #104557

#	Time	Username	Problem	Language	Result	Execution time	Memory
104557		minhtung0404	Examination (JOI19_examination)	C++17	100 / 100	1223 ms	53208 KiB

examination

#include<bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;

vector <int> mv;
int n, m, st[N], ans[N];

struct point{
    int s, t;

    bool operator < (const point&a) const {
        return (s + t) < (a.s + a.t);
    }
} a[N];

struct query{
    int x, y, z, id;

    bool operator < (const query&a) const {
        return z > a.z;
    }
} q[N];

struct node{
    vector <int> mv;
    vector <int> bit;
    int n, cnt;

    void init(){
        sort(mv.begin(), mv.end());
        mv.resize(unique(mv.begin(), mv.end()) - mv.begin());
        n = mv.size();
        bit.resize(mv.size());
    }

    void update(int i){
        i = lower_bound(mv.begin(), mv.end(), i) - mv.begin();
        i++; cnt++;
        while (i <= n){
            bit[i-1]++;
            i += i&(-i);
        }
    }

    int get(int i){
        i = lower_bound(mv.begin(), mv.end(), i) - mv.begin();
        int ans = 0;
        while (i > 0){
            ans += bit[i-1];
            i -= i&(-i);
        }
        return cnt - ans;
    }
} it[N << 2];

void update(int i, int l, int r, int pos, int val){
    if (l > pos || pos > r) return;
    it[i].update(val);
    if (l == r) return;
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, pos, val); update(i << 1 | 1, mid+1, r, pos, val);
}

int get(int i, int l, int r, int L, int R, int val){
    if (L > r || l > R) return 0;
    if (L <= l && r <= R) return it[i].get(val);
    int mid = (l + r) >> 1;
    return get(i << 1, l, mid, L, R, val) + get(i << 1 | 1, mid+1, r, L, R, val);
}

void prep(int i, int l, int r){
    if (l == r) {
        st[l] = i;
        return;
    }
    int mid = (l + r) >> 1;
    prep(i << 1, l, mid); prep(i << 1 | 1, mid+1, r);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].s >> a[i].t, mv.push_back(a[i].s);
    sort(a+1, a+1+n); sort(mv.begin(), mv.end());

    mv.resize(unique(mv.begin(), mv.end()) - mv.begin());
    int MAX = (int)mv.size();
    prep(1, 1, MAX);
    for (int i = 1; i <= n; i++){
        int node = st[lower_bound(mv.begin(), mv.end(), a[i].s) - mv.begin() + 1];
        while (node) it[node]. mv.push_back(a[i].t), node >>= 1;
    }
    for (int i = 0; i < N << 2; i++) it[i].init();

    for (int i = 1; i <= m; i++){
        q[i].id = i;
        cin >> q[i].x >> q[i].y >> q[i].z;
    }
    sort(q+1, q+1+m);

    int cur = n;
    for (int i = 1; i <= m; i++){
        while (cur && a[cur].s + a[cur].t >= q[i].z) {
            update(1, 1, MAX, lower_bound(mv.begin(), mv.end(), a[cur].s) - mv.begin() + 1, a[cur].t);
            cur--;
        }
        ans[q[i].id] = get(1, 1, MAX, lower_bound(mv.begin(), mv.end(), q[i].x) - mv.begin() + 1, MAX, q[i].y);
    }

    for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
}

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