oj.uz

Submission #716184

# Submission time Handle Problem Language Result Execution time Memory
716184 2023-03-29T08:12:50 Z TheSahib Examination (JOI19_examination) C++17
20 / 100
 3000 ms 577532 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){
        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;

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:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d %d", &scores[i].first, &scores[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         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 295 ms 306400 KB Output is correct
2 Correct 263 ms 306384 KB Output is correct
3 Correct 301 ms 306396 KB Output is correct
4 Incorrect 272 ms 306276 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 2777 ms 577532 KB Output is correct
2 Correct 2522 ms 577276 KB Output is correct
3 Correct 2521 ms 577376 KB Output is correct
4 Correct 1547 ms 357896 KB Output is correct
5 Correct 1063 ms 365052 KB Output is correct
6 Correct 515 ms 309736 KB Output is correct
7 Correct 2429 ms 577324 KB Output is correct
8 Correct 2424 ms 577160 KB Output is correct
9 Correct 2307 ms 577308 KB Output is correct
10 Correct 935 ms 360832 KB Output is correct
11 Correct 1498 ms 343716 KB Output is correct
12 Correct 506 ms 309340 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 577532 KB Output is correct
2 Correct 2522 ms 577276 KB Output is correct
3 Correct 2521 ms 577376 KB Output is correct
4 Correct 1547 ms 357896 KB Output is correct
5 Correct 1063 ms 365052 KB Output is correct
6 Correct 515 ms 309736 KB Output is correct
7 Correct 2429 ms 577324 KB Output is correct
8 Correct 2424 ms 577160 KB Output is correct
9 Correct 2307 ms 577308 KB Output is correct
10 Correct 935 ms 360832 KB Output is correct
11 Correct 1498 ms 343716 KB Output is correct
12 Correct 506 ms 309340 KB Output is correct
13 Execution timed out 3098 ms 576812 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 306400 KB Output is correct
2 Correct 263 ms 306384 KB Output is correct
3 Correct 301 ms 306396 KB Output is correct
4 Incorrect 272 ms 306276 KB Output isn't correct
5 Halted 0 ms 0 KB -