oj.uz

Submission #716176

# Submission time Handle Problem Language Result Execution time Memory
716176 2023-03-29T07:46:26 Z TheSahib Examination (JOI19_examination) C++17
0 / 100
 3000 ms 846472 KB 
#include <bits/stdc++.h>
 
 
#define ll long long
#define pii pair<int, int>
 
using namespace std;
 
const int TREE_SIZE = 1e5 * 30;
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];
}

SegTree2D tree;
 
int main(){
    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 478 ms 540500 KB Output is correct
2 Correct 488 ms 540480 KB Output is correct
3 Correct 521 ms 540468 KB Output is correct
4 Correct 484 ms 540516 KB Output is correct
5 Correct 506 ms 540524 KB Output is correct
6 Correct 495 ms 540516 KB Output is correct
7 Correct 782 ms 573528 KB Output is correct
8 Correct 784 ms 573440 KB Output is correct
9 Correct 745 ms 573560 KB Output is correct
10 Correct 729 ms 564036 KB Output is correct
11 Correct 707 ms 561260 KB Output is correct
12 Incorrect 543 ms 540540 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 846472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 846472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 540500 KB Output is correct
2 Correct 488 ms 540480 KB Output is correct
3 Correct 521 ms 540468 KB Output is correct
4 Correct 484 ms 540516 KB Output is correct
5 Correct 506 ms 540524 KB Output is correct
6 Correct 495 ms 540516 KB Output is correct
7 Correct 782 ms 573528 KB Output is correct
8 Correct 784 ms 573440 KB Output is correct
9 Correct 745 ms 573560 KB Output is correct
10 Correct 729 ms 564036 KB Output is correct
11 Correct 707 ms 561260 KB Output is correct
12 Incorrect 543 ms 540540 KB Output isn't correct
13 Halted 0 ms 0 KB -