oj.uz

Submission #715229

# Submission time Handle Problem Language Result Execution time Memory
715229 2023-03-26T08:42:21 Z TheSahib Examination (JOI19_examination) C++17
0 / 100
 2816 ms 1003760 KB 
#include <bits/stdc++.h>


#define ll long long
#define pii pair<int, int>

using namespace std;

const int TREE_SIZE = 1e5 * 40;
const int MAXVAL = (1 << 20) - 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];
}

int main(){
    SegTree2D tree;
    int n, q; cin >> n >> q;
    vector<pii> scores(n);
    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.begin(), scores.end(), comp1);
    vector<array<int, 4>> querries(q);
    for (int i = 0; i < q; i++)
    {
        cin >> querries[i][0] >> querries[i][1] >> querries[i][2];
        querries[i][3] = i;
    }
    sort(querries.begin(), querries.end(), 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.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 720392 KB Output is correct
2 Correct 728 ms 720468 KB Output is correct
3 Correct 667 ms 720460 KB Output is correct
4 Incorrect 627 ms 720440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2816 ms 1003760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2816 ms 1003760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 720392 KB Output is correct
2 Correct 728 ms 720468 KB Output is correct
3 Correct 667 ms 720460 KB Output is correct
4 Incorrect 627 ms 720440 KB Output isn't correct
5 Halted 0 ms 0 KB -