oj.uz

Submission #715218

# Submission time Handle Problem Language Result Execution time Memory
715218 2023-03-26T08:34:14 Z TheSahib Examination (JOI19_examination) C++17
0 / 100
 1073 ms 312756 KB 
#include <bits/stdc++.h>


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

using namespace std;

const int TREE_SIZE = 1e5;
const int MAXVAL = (1 << 30) - 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 19 ms 18260 KB Output is correct
2 Correct 18 ms 18240 KB Output is correct
3 Correct 22 ms 18288 KB Output is correct
4 Correct 19 ms 18388 KB Output is correct
5 Correct 27 ms 18348 KB Output is correct
6 Correct 20 ms 18404 KB Output is correct
7 Correct 177 ms 51280 KB Output is correct
8 Correct 167 ms 51284 KB Output is correct
9 Correct 180 ms 51340 KB Output is correct
10 Correct 140 ms 41880 KB Output is correct
11 Correct 121 ms 39036 KB Output is correct
12 Incorrect 50 ms 18388 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1073 ms 312756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1073 ms 312756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18260 KB Output is correct
2 Correct 18 ms 18240 KB Output is correct
3 Correct 22 ms 18288 KB Output is correct
4 Correct 19 ms 18388 KB Output is correct
5 Correct 27 ms 18348 KB Output is correct
6 Correct 20 ms 18404 KB Output is correct
7 Correct 177 ms 51280 KB Output is correct
8 Correct 167 ms 51284 KB Output is correct
9 Correct 180 ms 51340 KB Output is correct
10 Correct 140 ms 41880 KB Output is correct
11 Correct 121 ms 39036 KB Output is correct
12 Incorrect 50 ms 18388 KB Output isn't correct
13 Halted 0 ms 0 KB -