oj.uz

Submission #747642

# Submission time Handle Problem Language Result Execution time Memory
747642 2023-05-24T12:33:54 Z TahirAliyev Examination (JOI19_examination) C++17
100 / 100
 1720 ms 210180 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<int, int>

const int MAX = 1e5 + 5;
const int LOGMAX = 30;
const int treeSize = MAX * LOGMAX * LOGMAX;

int tree[treeSize];
int L[treeSize], R[treeSize];

int n, m;
int nxt = MAX * 4;

void update1d(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] = ++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(node == 0) return 0;
    if(r < ql || qr < l) return 0;
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return ask1d(L[node], l, mid, ql, qr) + ask1d(R[node], mid + 1, r, ql, qr);
}

void update2d(int node, int l, int r, int posx, int posy, int val){
    update1d(node, 0, n, posx, val);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(posy <= mid){
        update2d(2 * node, l, mid, posx, posy, val);
    }
    else{
        update2d(2 * node + 1, mid + 1, r, posx, posy, val);
    }
}

int ask2d(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 ask1d(node, 0, n, x1, x2);
    int mid = (l + r) / 2;
    return ask2d(2 * node, l, mid, x1, x2, y1, y2) + ask2d(2 * node + 1, mid + 1, r, x1, x2, y1, y2);
}


bool comp(array<int, 4> a, array<int, 4> b){
    return (a[2] < b[2]);
}

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

pii arr[MAX];
vector<int> v1, v2;
vector<array<int, 4>> q;

void INPUT(){
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &arr[i].first, &arr[i].second);
        v1.push_back(arr[i].first);
        v2.push_back(arr[i].second);
    }
    sort(arr, arr + n, comp2);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    for (int i = 0; i < m; i++)
    {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        q.push_back({a, b, c, i});
    }
    sort(q.begin(), q.end(), comp);
}

int main(){
    INPUT();
    for (int i = 0; i < n; i++)
    {
        int a = lower_bound(v1.begin(), v1.end(), arr[i].first) - v1.begin();
        int b = lower_bound(v2.begin(), v2.end(), arr[i].second) - v2.begin();
        update2d(1, 0, n, a, b, 1);
    }
    int p = 0;
    int ans[m];
    for(array<int, 4>& t : q){
        int X = lower_bound(v1.begin(), v1.end(), t[0]) - v1.begin();
        int Y = lower_bound(v2.begin(), v2.end(), t[1]) - v2.begin();
        while(p != n && t[2] > arr[p].first + arr[p].second){
            int a = lower_bound(v1.begin(), v1.end(), arr[p].first) - v1.begin();
            int b = lower_bound(v2.begin(), v2.end(), arr[p].second) - v2.begin();
            update2d(1, 0, n, a, b, -1);
            p++;
        }
        ans[t[3]] = ask2d(1, 0, n, X, n, Y, n);
    }
    for(int a: ans){
        cout << a << '\n';
    }
}

Compilation message

examination.cpp: In function 'void INPUT()':
examination.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%d%d", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:88:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         int a, b, c; scanf("%d%d%d", &a, &b, &c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 320 KB Output is correct
7 Correct 13 ms 3796 KB Output is correct
8 Correct 13 ms 3896 KB Output is correct
9 Correct 13 ms 3796 KB Output is correct
10 Correct 9 ms 2604 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 6 ms 712 KB Output is correct
13 Correct 10 ms 3800 KB Output is correct
14 Correct 10 ms 3788 KB Output is correct
15 Correct 10 ms 3872 KB Output is correct
16 Correct 4 ms 1236 KB Output is correct
17 Correct 6 ms 1588 KB Output is correct
18 Correct 5 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 203160 KB Output is correct
2 Correct 1118 ms 203044 KB Output is correct
3 Correct 1087 ms 203148 KB Output is correct
4 Correct 376 ms 95460 KB Output is correct
5 Correct 437 ms 95544 KB Output is correct
6 Correct 200 ms 5556 KB Output is correct
7 Correct 946 ms 203156 KB Output is correct
8 Correct 1070 ms 203216 KB Output is correct
9 Correct 811 ms 202996 KB Output is correct
10 Correct 189 ms 27536 KB Output is correct
11 Correct 203 ms 38060 KB Output is correct
12 Correct 131 ms 4280 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 203160 KB Output is correct
2 Correct 1118 ms 203044 KB Output is correct
3 Correct 1087 ms 203148 KB Output is correct
4 Correct 376 ms 95460 KB Output is correct
5 Correct 437 ms 95544 KB Output is correct
6 Correct 200 ms 5556 KB Output is correct
7 Correct 946 ms 203156 KB Output is correct
8 Correct 1070 ms 203216 KB Output is correct
9 Correct 811 ms 202996 KB Output is correct
10 Correct 189 ms 27536 KB Output is correct
11 Correct 203 ms 38060 KB Output is correct
12 Correct 131 ms 4280 KB Output is correct
13 Correct 1685 ms 203184 KB Output is correct
14 Correct 1354 ms 203212 KB Output is correct
15 Correct 1139 ms 203260 KB Output is correct
16 Correct 536 ms 94368 KB Output is correct
17 Correct 585 ms 95920 KB Output is correct
18 Correct 232 ms 5528 KB Output is correct
19 Correct 1720 ms 203168 KB Output is correct
20 Correct 1598 ms 203252 KB Output is correct
21 Correct 1552 ms 203156 KB Output is correct
22 Correct 186 ms 27568 KB Output is correct
23 Correct 205 ms 38060 KB Output is correct
24 Correct 142 ms 4272 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 320 KB Output is correct
7 Correct 13 ms 3796 KB Output is correct
8 Correct 13 ms 3896 KB Output is correct
9 Correct 13 ms 3796 KB Output is correct
10 Correct 9 ms 2604 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 6 ms 712 KB Output is correct
13 Correct 10 ms 3800 KB Output is correct
14 Correct 10 ms 3788 KB Output is correct
15 Correct 10 ms 3872 KB Output is correct
16 Correct 4 ms 1236 KB Output is correct
17 Correct 6 ms 1588 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 1147 ms 203160 KB Output is correct
20 Correct 1118 ms 203044 KB Output is correct
21 Correct 1087 ms 203148 KB Output is correct
22 Correct 376 ms 95460 KB Output is correct
23 Correct 437 ms 95544 KB Output is correct
24 Correct 200 ms 5556 KB Output is correct
25 Correct 946 ms 203156 KB Output is correct
26 Correct 1070 ms 203216 KB Output is correct
27 Correct 811 ms 202996 KB Output is correct
28 Correct 189 ms 27536 KB Output is correct
29 Correct 203 ms 38060 KB Output is correct
30 Correct 131 ms 4280 KB Output is correct
31 Correct 1685 ms 203184 KB Output is correct
32 Correct 1354 ms 203212 KB Output is correct
33 Correct 1139 ms 203260 KB Output is correct
34 Correct 536 ms 94368 KB Output is correct
35 Correct 585 ms 95920 KB Output is correct
36 Correct 232 ms 5528 KB Output is correct
37 Correct 1720 ms 203168 KB Output is correct
38 Correct 1598 ms 203252 KB Output is correct
39 Correct 1552 ms 203156 KB Output is correct
40 Correct 186 ms 27568 KB Output is correct
41 Correct 205 ms 38060 KB Output is correct
42 Correct 142 ms 4272 KB Output is correct
43 Correct 1562 ms 210068 KB Output is correct
44 Correct 1554 ms 210180 KB Output is correct
45 Correct 1328 ms 210100 KB Output is correct
46 Correct 533 ms 100164 KB Output is correct
47 Correct 562 ms 102320 KB Output is correct
48 Correct 273 ms 6364 KB Output is correct
49 Correct 1158 ms 210060 KB Output is correct
50 Correct 1545 ms 210148 KB Output is correct
51 Correct 1084 ms 209876 KB Output is correct
52 Correct 292 ms 36260 KB Output is correct
53 Correct 213 ms 49276 KB Output is correct