oj.uz

Submission #731685

# Submission time Handle Problem Language Result Execution time Memory
731685 2023-04-27T19:05:13 Z TheSahib Examination (JOI19_examination) C++17
100 / 100
 1890 ms 211840 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;
}
bool comp2(pii a, pii b){
    return a.second < b.second;
}

pii arr[MAX];
pii xSort[MAX];
pii ySort[MAX];
pii compress[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);
        xSort[i] = arr[i];
        ySort[i] = arr[i];
    }
    
    sort(arr, arr + n, comp);
    sort(xSort, xSort + n);
    sort(ySort, ySort + n, comp2);

    for (int i = 0; i < n; i++)
    {
        compress[i] = {lower_bound(xSort, xSort + n, arr[i]) - xSort, 
                        lower_bound(ySort, ySort + n, arr[i], comp2) - ySort};
        update(0, 0, MAX, compress[i].first, compress[i].second, 1);
    }

    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, compress[last].first, compress[last].second, -1);
            ++last;
        }
        int x = lower_bound(xSort, xSort + n, make_pair(q[i][1], -1)) - xSort;
        int y = lower_bound(ySort, ySort + n, make_pair(-1, q[i][2]), comp2) - ySort;
        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:83:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d %d", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d %d %d", &q[i][1], &q[i][2], &q[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 17 ms 4604 KB Output is correct
8 Correct 17 ms 4608 KB Output is correct
9 Correct 20 ms 4548 KB Output is correct
10 Correct 12 ms 2900 KB Output is correct
11 Correct 15 ms 3820 KB Output is correct
12 Correct 11 ms 884 KB Output is correct
13 Correct 16 ms 4576 KB Output is correct
14 Correct 13 ms 4500 KB Output is correct
15 Correct 13 ms 4540 KB Output is correct
16 Correct 8 ms 2900 KB Output is correct
17 Correct 11 ms 1956 KB Output is correct
18 Correct 8 ms 616 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 205820 KB Output is correct
2 Correct 1087 ms 205848 KB Output is correct
3 Correct 1113 ms 205840 KB Output is correct
4 Correct 360 ms 96968 KB Output is correct
5 Correct 419 ms 127276 KB Output is correct
6 Correct 192 ms 7008 KB Output is correct
7 Correct 1097 ms 205784 KB Output is correct
8 Correct 965 ms 205788 KB Output is correct
9 Correct 846 ms 205744 KB Output is correct
10 Correct 260 ms 67404 KB Output is correct
11 Correct 209 ms 39320 KB Output is correct
12 Correct 153 ms 5704 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 205820 KB Output is correct
2 Correct 1087 ms 205848 KB Output is correct
3 Correct 1113 ms 205840 KB Output is correct
4 Correct 360 ms 96968 KB Output is correct
5 Correct 419 ms 127276 KB Output is correct
6 Correct 192 ms 7008 KB Output is correct
7 Correct 1097 ms 205784 KB Output is correct
8 Correct 965 ms 205788 KB Output is correct
9 Correct 846 ms 205744 KB Output is correct
10 Correct 260 ms 67404 KB Output is correct
11 Correct 209 ms 39320 KB Output is correct
12 Correct 153 ms 5704 KB Output is correct
13 Correct 1791 ms 205724 KB Output is correct
14 Correct 1555 ms 205796 KB Output is correct
15 Correct 1100 ms 205768 KB Output is correct
16 Correct 614 ms 95440 KB Output is correct
17 Correct 668 ms 127192 KB Output is correct
18 Correct 250 ms 6968 KB Output is correct
19 Correct 1878 ms 205908 KB Output is correct
20 Correct 1890 ms 205848 KB Output is correct
21 Correct 1767 ms 205844 KB Output is correct
22 Correct 268 ms 67500 KB Output is correct
23 Correct 210 ms 39232 KB Output is correct
24 Correct 154 ms 5704 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 17 ms 4604 KB Output is correct
8 Correct 17 ms 4608 KB Output is correct
9 Correct 20 ms 4548 KB Output is correct
10 Correct 12 ms 2900 KB Output is correct
11 Correct 15 ms 3820 KB Output is correct
12 Correct 11 ms 884 KB Output is correct
13 Correct 16 ms 4576 KB Output is correct
14 Correct 13 ms 4500 KB Output is correct
15 Correct 13 ms 4540 KB Output is correct
16 Correct 8 ms 2900 KB Output is correct
17 Correct 11 ms 1956 KB Output is correct
18 Correct 8 ms 616 KB Output is correct
19 Correct 1049 ms 205820 KB Output is correct
20 Correct 1087 ms 205848 KB Output is correct
21 Correct 1113 ms 205840 KB Output is correct
22 Correct 360 ms 96968 KB Output is correct
23 Correct 419 ms 127276 KB Output is correct
24 Correct 192 ms 7008 KB Output is correct
25 Correct 1097 ms 205784 KB Output is correct
26 Correct 965 ms 205788 KB Output is correct
27 Correct 846 ms 205744 KB Output is correct
28 Correct 260 ms 67404 KB Output is correct
29 Correct 209 ms 39320 KB Output is correct
30 Correct 153 ms 5704 KB Output is correct
31 Correct 1791 ms 205724 KB Output is correct
32 Correct 1555 ms 205796 KB Output is correct
33 Correct 1100 ms 205768 KB Output is correct
34 Correct 614 ms 95440 KB Output is correct
35 Correct 668 ms 127192 KB Output is correct
36 Correct 250 ms 6968 KB Output is correct
37 Correct 1878 ms 205908 KB Output is correct
38 Correct 1890 ms 205848 KB Output is correct
39 Correct 1767 ms 205844 KB Output is correct
40 Correct 268 ms 67500 KB Output is correct
41 Correct 210 ms 39232 KB Output is correct
42 Correct 154 ms 5704 KB Output is correct
43 Correct 1829 ms 211840 KB Output is correct
44 Correct 1815 ms 211668 KB Output is correct
45 Correct 1631 ms 211576 KB Output is correct
46 Correct 567 ms 101384 KB Output is correct
47 Correct 682 ms 133772 KB Output is correct
48 Correct 285 ms 7936 KB Output is correct
49 Correct 1412 ms 211604 KB Output is correct
50 Correct 1769 ms 211812 KB Output is correct
51 Correct 1259 ms 211376 KB Output is correct
52 Correct 412 ms 87932 KB Output is correct
53 Correct 220 ms 50640 KB Output is correct