Submission #716179

#	Time	Username	Problem	Language	Result	Execution time	Memory
716179		TheSahib	Examination (JOI19_examination)	C++17	0 / 100	2100 ms	578572 KiB

examination

#include <bits/stdc++.h>
 
 
#define ll long long
#define pii pair<int, int>
 
using namespace std;
 
const int MAX = 1e5 + 5;
const int TREE_SIZE = MAX * 17;
const int MAXVAL = (1 << 17) - 1;
 
struct SegTree1D{
    vector<int> tree, L, R;
    int nxt = 0;
    SegTree1D(){
        addNode();
    }
    int addNode(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
        return nxt++;
    }
    void update(int node, int l, int r, int pos, int val){
        tree[node] += val;
        if(l == r) return;
        int mid = (l + r) / 2;
        if(pos <= mid){
            if(!L[node]) L[node] = addNode();
            update(L[node], l, mid, pos, val);
        }
        else{
            if(!R[node]) R[node] = addNode();
            update(R[node], mid + 1, r, pos, val);
        }
    }
 
    int ask(int node, int l, int r, int ql, int qr){
        if(r < ql || qr < l) return 0;
        if(ql <= l && r <= qr) return tree[node];
        
        int ans = 0;
        int mid = (l + r) / 2;
        if(L[node]) ans += ask(L[node], l, mid, ql, qr);
        if(R[node]) ans += ask(R[node], mid + 1, r, ql, qr);
        return ans;
    }
};
 
struct SegTree2D{
    SegTree1D tree[TREE_SIZE];
    int L[TREE_SIZE], R[TREE_SIZE];
    int nxt = 0;
 
    int addNode(){
        return nxt++;
    }
 
    SegTree2D(){
        addNode();
        memset(L, 0, sizeof(L));
        memset(R, 0, sizeof(R));
    }
    void update(int node, int l, int r, int ux, int uy, int val){
        tree[node].update(0, 0, MAXVAL, ux, val);
        if(l == r) return;
        int mid = (l + r) / 2;
        if(uy <= mid){
            if(!L[node]) L[node] = addNode();
            update(L[node], l, mid, ux, uy, val);
        }
        else{
            if(!R[node]) R[node] = addNode();
            update(R[node], mid + 1, r, ux, uy, val);
        }
    }
    int ask(int node, int l, int r, int x1, int x2, int y1, int y2){
        if(r < y1 || y2 < l) return 0;
        if(y1 <= l && r <= y2) return tree[node].ask(0, 0, MAXVAL, x1, x2);
        
        int ans = 0;
        int mid = (l + r) / 2;
        if(L[node]) ans += ask(L[node], l, mid, x1, x2, y1, y2);
        if(R[node]) ans += ask(R[node], mid + 1, r, x1, x2, y1, y2);
        return ans;
    }
};


bool comp1(pii p1, pii p2){
    return (p1.first + p1.second) < (p2.first + p2.second);
}

bool comp2(array<int, 4>& a1, array<int, 4>& a2){
    return a1[2] < a2[2];
}

SegTree2D tree;

pii scores[MAX];
array<int, 4> querries[MAX];

int main(){
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> scores[i].first >> scores[i].second;
        tree.update(0, 0, MAXVAL, scores[i].first, scores[i].second, 1);
    }
    sort(scores, scores + n, comp1);
    for (int i = 0; i < q; i++)
    {
        cin >> querries[i][0] >> querries[i][1] >> querries[i][2];
        querries[i][3] = i;
    }
    sort(querries, querries + q, comp2);
 
    int ans[q];
    int last = 0;
    for (int i = 0; i < q; i++)
    {
        int l = 0, r = n - 1;
        int low = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            if(scores[mid].first + scores[mid].second < querries[i][2]){
                l = mid + 1;
                low = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        while(last < low){
            tree.update(0, 0, MAXVAL, scores[last].first, scores[last].second, -1);
            last++;
        }
        ans[querries[i][3]] = n - last;
        if(querries[i][0] != 0){
            ans[querries[i][3]] -= tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, MAXVAL);
        }
        if(querries[i][1] != 0){
            ans[querries[i][3]] -= tree.ask(0, 0, MAXVAL, 0, MAXVAL, 0, querries[i][1] - 1);
        }
        if(querries[i][1] != 0 && querries[i][2] != 0){
            ans[querries[i][3]] += tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, querries[i][1] - 1);
        }
    }
    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << '\n';
    }
}

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