oj.uz

Submission #731683

# Submission time Handle Problem Language Result Execution time Memory
731683 2023-04-27T18:48:08 Z TheSahib Examination (JOI19_examination) C++14
41 / 100
 2052 ms 203396 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 * 17;
const int MAXVAL = (1 << 17) - 1;

int tree1D[TREE_SIZE], L[TREE_SIZE], R[TREE_SIZE];
int nxt = MAX * 4;

void update1D(int node, int l, int r, int pos, int val){
    tree1D[node] += val;
    if(l == r) return;
    int mid = (l + r) / 2;
    if(pos <= mid){
        if(!L[node]) L[node] = ++nxt;
        update1D(L[node], l, mid, pos, val);
    }
    else{
        if(!R[node]) R[node] = ++nxt;
        update1D(R[node], mid + 1, r, pos, val);
    }
}

int ask1D(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l){
        return 0;
    }
    if(ql <= l && r <= qr){
        return tree1D[node];
    }
    int mid = (l + r) / 2;
    int ans = 0;

    if(L[node]) ans += ask1D(L[node], l, mid, ql, qr);
    if(R[node]) ans += ask1D(R[node], mid + 1, r, ql, qr);

    return ans;
}

void update(int node, int l, int r, int x, int y, int val){
    update1D(node, 0, MAXVAL, x, val);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(y <= mid){
        update(node * 2 + 1, l, mid, x, y, val);
    }
    else{
        update((node + 1) * 2, mid + 1, r, x, y, val);
    }
}

int ask(int node, int l, int r, int x1, int y1, int x2, int y2){
    if(y1 > r || y2 < l){
        return 0;
    }
    if(y1 <= l && r <= y2){
        return ask1D(node, 0, MAXVAL, x1, x2);
    }
    int mid = (l + r) / 2;
    return ask(node * 2 + 1, l, mid, x1, y1, x2, y2) + ask((node + 1) * 2, mid + 1, r, x1, y1, x2, y2);
}

bool comp(pii a, pii b){
    return a.first + a.second < b.first + b.second;
}

pii arr[MAX];
array<int, 4> q[MAX];
int ans[MAX];
int main(){
    int n, m; scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &arr[i].first, &arr[i].second);
        update(0, 0, MAX, arr[i].first, arr[i].second, 1);
    }
    
    sort(arr, arr + n, comp);

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &q[i][1], &q[i][2], &q[i][0]);
        q[i][3] = i;
    }
    sort(q, q + m);
    int last = 0;
    for (int i = 0; i < m; i++)
    {
        while(last != n && arr[last].first + arr[last].second < q[i][0]){
            update(0, 0, MAX, arr[last].first, arr[last].second, -1);
            ++last;
        }
        int x = q[i][1], y = q[i][2];
        ans[q[i][3]] = ask(0, 0, MAX, x, y, MAX, MAX);
    }
    for (int i = 0; i < m; i++)
    {
        cout << ans[i] << '\n';
    }
    
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:77:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d %d", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d %d", &q[i][1], &q[i][2], &q[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Incorrect 1 ms 304 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 1187 ms 203232 KB Output is correct
2 Correct 1192 ms 203336 KB Output is correct
3 Correct 1148 ms 203396 KB Output is correct
4 Correct 426 ms 46464 KB Output is correct
5 Correct 494 ms 47316 KB Output is correct
6 Correct 183 ms 4676 KB Output is correct
7 Correct 1193 ms 203352 KB Output is correct
8 Correct 962 ms 203268 KB Output is correct
9 Correct 996 ms 203312 KB Output is correct
10 Correct 331 ms 28108 KB Output is correct
11 Correct 285 ms 38192 KB Output is correct
12 Correct 157 ms 4216 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 203232 KB Output is correct
2 Correct 1192 ms 203336 KB Output is correct
3 Correct 1148 ms 203396 KB Output is correct
4 Correct 426 ms 46464 KB Output is correct
5 Correct 494 ms 47316 KB Output is correct
6 Correct 183 ms 4676 KB Output is correct
7 Correct 1193 ms 203352 KB Output is correct
8 Correct 962 ms 203268 KB Output is correct
9 Correct 996 ms 203312 KB Output is correct
10 Correct 331 ms 28108 KB Output is correct
11 Correct 285 ms 38192 KB Output is correct
12 Correct 157 ms 4216 KB Output is correct
13 Correct 2052 ms 203304 KB Output is correct
14 Correct 1629 ms 203208 KB Output is correct
15 Correct 1108 ms 203280 KB Output is correct
16 Correct 652 ms 46956 KB Output is correct
17 Correct 667 ms 47704 KB Output is correct
18 Correct 225 ms 4680 KB Output is correct
19 Correct 1822 ms 203044 KB Output is correct
20 Correct 1799 ms 203076 KB Output is correct
21 Correct 1859 ms 202428 KB Output is correct
22 Correct 309 ms 27680 KB Output is correct
23 Correct 253 ms 37828 KB Output is correct
24 Correct 151 ms 3496 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Halted 0 ms 0 KB -