oj.uz

Submission #716199

# Submission time Handle Problem Language Result Execution time Memory
716199 2023-03-29T08:34:24 Z TheSahib Examination (JOI19_examination) C++17
20 / 100
 3000 ms 577528 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(l != r){
            tree[node] += val;
            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;
            }
        }
        tree[node] += 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) >> 1;
        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(l != r){
            tree[node].update(0, 0, MAXVAL, ux, val);
            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;
            }
        }
        tree[node].update(0, 0, MAXVAL, ux, 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) >> 1;
        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 307 ms 306356 KB Output is correct
2 Correct 287 ms 306452 KB Output is correct
3 Correct 383 ms 306412 KB Output is correct
4 Incorrect 289 ms 306472 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 2578 ms 577528 KB Output is correct
2 Correct 2413 ms 577192 KB Output is correct
3 Correct 2555 ms 577328 KB Output is correct
4 Correct 1476 ms 358000 KB Output is correct
5 Correct 1012 ms 365164 KB Output is correct
6 Correct 495 ms 309656 KB Output is correct
7 Correct 2435 ms 577328 KB Output is correct
8 Correct 2271 ms 577168 KB Output is correct
9 Correct 2213 ms 577436 KB Output is correct
10 Correct 898 ms 360776 KB Output is correct
11 Correct 1284 ms 343800 KB Output is correct
12 Correct 457 ms 309300 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2578 ms 577528 KB Output is correct
2 Correct 2413 ms 577192 KB Output is correct
3 Correct 2555 ms 577328 KB Output is correct
4 Correct 1476 ms 358000 KB Output is correct
5 Correct 1012 ms 365164 KB Output is correct
6 Correct 495 ms 309656 KB Output is correct
7 Correct 2435 ms 577328 KB Output is correct
8 Correct 2271 ms 577168 KB Output is correct
9 Correct 2213 ms 577436 KB Output is correct
10 Correct 898 ms 360776 KB Output is correct
11 Correct 1284 ms 343800 KB Output is correct
12 Correct 457 ms 309300 KB Output is correct
13 Execution timed out 3089 ms 576788 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 306356 KB Output is correct
2 Correct 287 ms 306452 KB Output is correct
3 Correct 383 ms 306412 KB Output is correct
4 Incorrect 289 ms 306472 KB Output isn't correct
5 Halted 0 ms 0 KB -