oj.uz

Submission #716197

# Submission time Handle Problem Language Result Execution time Memory
716197 2023-03-29T08:31:25 Z TheSahib Examination (JOI19_examination) C++17
20 / 100
 3000 ms 577628 KB 
#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){
        int mid = 0;
        while(true){
            tree[node] += val;
            if(l == r) return;
            mid = (l + r) >> 1;
            if(pos <= mid){
                if(!L[node]) L[node] = addNode();
                node = L[node];
                r = mid;
            }
            else{
                if(!R[node]) R[node] = addNode();
                node = R[node];
                l = mid + 1;
            }
        }
    }

    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){
        int mid = 0;
        while(true){
            tree[node].update(0, 0, MAXVAL, ux, val);
            if(l == r) return;
            mid = (l + r) >> 1;
            if(uy <= mid){
                if(!L[node]) L[node] = addNode();
                node = L[node];
                r = mid;
            }
            else{
                if(!R[node]) R[node] = addNode();
                node = R[node];
                l = mid + 1;
            }
        }
    }
    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 ans[MAX];

int main(){
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &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++)
    {
        scanf("%d%d%d", &querries[i][0], &querries[i][1], &querries[i][2]);
        querries[i][3] = i;
    }
    sort(querries, querries + q, comp2);
    int last = 0;
    for (int i = 0; i < q; i++)
    {
        while(last < n && scores[last].first + scores[last].second < querries[i][2]){
            tree.update(0, 0, MAXVAL, scores[last].first, scores[last].second, -1);
            last++;
        }
        ans[querries[i][3]] = tree.ask(0, 0, MAXVAL, querries[i][0], MAX, querries[i][1], MAX);
    }
    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%d %d", &scores[i].first, &scores[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%d%d%d", &querries[i][0], &querries[i][1], &querries[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 306328 KB Output is correct
2 Correct 304 ms 306404 KB Output is correct
3 Correct 294 ms 306460 KB Output is correct
4 Incorrect 310 ms 306360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2636 ms 577340 KB Output is correct
2 Correct 2517 ms 577128 KB Output is correct
3 Correct 2470 ms 577212 KB Output is correct
4 Correct 1512 ms 357884 KB Output is correct
5 Correct 1123 ms 365060 KB Output is correct
6 Correct 519 ms 309692 KB Output is correct
7 Correct 2389 ms 577416 KB Output is correct
8 Correct 2589 ms 577224 KB Output is correct
9 Correct 2213 ms 577628 KB Output is correct
10 Correct 871 ms 360872 KB Output is correct
11 Correct 1251 ms 343940 KB Output is correct
12 Correct 483 ms 309324 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2636 ms 577340 KB Output is correct
2 Correct 2517 ms 577128 KB Output is correct
3 Correct 2470 ms 577212 KB Output is correct
4 Correct 1512 ms 357884 KB Output is correct
5 Correct 1123 ms 365060 KB Output is correct
6 Correct 519 ms 309692 KB Output is correct
7 Correct 2389 ms 577416 KB Output is correct
8 Correct 2589 ms 577224 KB Output is correct
9 Correct 2213 ms 577628 KB Output is correct
10 Correct 871 ms 360872 KB Output is correct
11 Correct 1251 ms 343940 KB Output is correct
12 Correct 483 ms 309324 KB Output is correct
13 Execution timed out 3067 ms 576760 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 306328 KB Output is correct
2 Correct 304 ms 306404 KB Output is correct
3 Correct 294 ms 306460 KB Output is correct
4 Incorrect 310 ms 306360 KB Output isn't correct
5 Halted 0 ms 0 KB -