oj.uz

Submission #731681

# Submission time Handle Problem Language Result Execution time Memory
731681 2023-04-27T18:44:37 Z TheSahib Examination (JOI19_examination) C++17
41 / 100
 2179 ms 204076 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]] = n - last;
        if(x != 0){
            ans[q[i][3]] -= ask(0, 0, MAX, 0, 0, x - 1, MAX);
        }
        if(y != 0){
            ans[q[i][3]] -= ask(0, 0, MAX, 0, 0, MAX, y - 1);
        }
        if(x != 0 && y != 0){
            ans[q[i][3]] += ask(0, 0, MAX, 0, 0, x - 1, y - 1);
        }
    }
    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 340 KB Output is correct
4 Incorrect 1 ms 396 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 1200 ms 203664 KB Output is correct
2 Correct 1184 ms 203724 KB Output is correct
3 Correct 1246 ms 203632 KB Output is correct
4 Correct 446 ms 46428 KB Output is correct
5 Correct 479 ms 47312 KB Output is correct
6 Correct 186 ms 4640 KB Output is correct
7 Correct 1173 ms 203500 KB Output is correct
8 Correct 971 ms 203504 KB Output is correct
9 Correct 976 ms 203396 KB Output is correct
10 Correct 298 ms 28168 KB Output is correct
11 Correct 309 ms 38232 KB Output is correct
12 Correct 164 ms 4264 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 203664 KB Output is correct
2 Correct 1184 ms 203724 KB Output is correct
3 Correct 1246 ms 203632 KB Output is correct
4 Correct 446 ms 46428 KB Output is correct
5 Correct 479 ms 47312 KB Output is correct
6 Correct 186 ms 4640 KB Output is correct
7 Correct 1173 ms 203500 KB Output is correct
8 Correct 971 ms 203504 KB Output is correct
9 Correct 976 ms 203396 KB Output is correct
10 Correct 298 ms 28168 KB Output is correct
11 Correct 309 ms 38232 KB Output is correct
12 Correct 164 ms 4264 KB Output is correct
13 Correct 1921 ms 204072 KB Output is correct
14 Correct 1686 ms 203920 KB Output is correct
15 Correct 1236 ms 203724 KB Output is correct
16 Correct 679 ms 46896 KB Output is correct
17 Correct 776 ms 47816 KB Output is correct
18 Correct 234 ms 4676 KB Output is correct
19 Correct 2090 ms 204004 KB Output is correct
20 Correct 2053 ms 204000 KB Output is correct
21 Correct 2179 ms 204076 KB Output is correct
22 Correct 353 ms 28068 KB Output is correct
23 Correct 307 ms 38228 KB Output is correct
24 Correct 166 ms 4332 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 340 KB Output is correct
4 Incorrect 1 ms 396 KB Output isn't correct
5 Halted 0 ms 0 KB -