oj.uz

Submission #747641

# Submission time Handle Problem Language Result Execution time Memory
747641 2023-05-24T12:23:44 Z TahirAliyev Examination (JOI19_examination) C++17
41 / 100
 3000 ms 203396 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(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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Execution timed out 3072 ms 1020 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 203156 KB Output is correct
2 Correct 1172 ms 203220 KB Output is correct
3 Correct 1124 ms 203188 KB Output is correct
4 Correct 378 ms 95492 KB Output is correct
5 Correct 488 ms 95524 KB Output is correct
6 Correct 184 ms 5496 KB Output is correct
7 Correct 979 ms 203140 KB Output is correct
8 Correct 1066 ms 203172 KB Output is correct
9 Correct 855 ms 203076 KB Output is correct
10 Correct 187 ms 27580 KB Output is correct
11 Correct 209 ms 38052 KB Output is correct
12 Correct 141 ms 4184 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 203156 KB Output is correct
2 Correct 1172 ms 203220 KB Output is correct
3 Correct 1124 ms 203188 KB Output is correct
4 Correct 378 ms 95492 KB Output is correct
5 Correct 488 ms 95524 KB Output is correct
6 Correct 184 ms 5496 KB Output is correct
7 Correct 979 ms 203140 KB Output is correct
8 Correct 1066 ms 203172 KB Output is correct
9 Correct 855 ms 203076 KB Output is correct
10 Correct 187 ms 27580 KB Output is correct
11 Correct 209 ms 38052 KB Output is correct
12 Correct 141 ms 4184 KB Output is correct
13 Correct 1618 ms 203096 KB Output is correct
14 Correct 1375 ms 203296 KB Output is correct
15 Correct 1097 ms 203396 KB Output is correct
16 Correct 538 ms 94532 KB Output is correct
17 Correct 576 ms 95948 KB Output is correct
18 Correct 225 ms 5504 KB Output is correct
19 Correct 1576 ms 203168 KB Output is correct
20 Correct 1511 ms 203208 KB Output is correct
21 Correct 1551 ms 203072 KB Output is correct
22 Correct 202 ms 27612 KB Output is correct
23 Correct 202 ms 38016 KB Output is correct
24 Correct 131 ms 4256 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Execution timed out 3072 ms 1020 KB Time limit exceeded
5 Halted 0 ms 0 KB -