oj.uz

Submission #747632

# Submission time Handle Problem Language Result Execution time Memory
747632 2023-05-24T12:11:42 Z TahirAliyev Examination (JOI19_examination) C++17
41 / 100
 3000 ms 203312 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, 1, 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, 1, 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(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() + 1;
        int b = lower_bound(v2.begin(), v2.end(), arr[i].second) - v2.begin() + 1;
        update2d(1, 1, n, a, b, 1);
    }
    sort(arr, arr + n, comp2);
    int p = 0;
    int ans[m];
    for(array<int, 4> t : q){
        int X = lower_bound(v1.begin(), v1.end(), t[0]) - v1.begin() + 1;
        int Y = lower_bound(v2.begin(), v2.end(), t[1]) - v2.begin() + 1;
        while(t[2] > arr[p].first + arr[p].second){
            int a = lower_bound(v1.begin(), v1.end(), arr[p].first) - v1.begin() + 1;
            int b = lower_bound(v2.begin(), v2.end(), arr[p].second) - v2.begin() + 1;
            update2d(1, 1, n, a, b, -1);
            p++;
        }
        ans[t[3]] = ask2d(1, 1, 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:87:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         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 3086 ms 1188 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 203184 KB Output is correct
2 Correct 1233 ms 203260 KB Output is correct
3 Correct 1215 ms 203100 KB Output is correct
4 Correct 594 ms 96028 KB Output is correct
5 Correct 621 ms 96096 KB Output is correct
6 Correct 202 ms 5560 KB Output is correct
7 Correct 1135 ms 203056 KB Output is correct
8 Correct 1252 ms 203176 KB Output is correct
9 Correct 994 ms 203108 KB Output is correct
10 Correct 258 ms 27560 KB Output is correct
11 Correct 289 ms 38040 KB Output is correct
12 Correct 127 ms 4184 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 203184 KB Output is correct
2 Correct 1233 ms 203260 KB Output is correct
3 Correct 1215 ms 203100 KB Output is correct
4 Correct 594 ms 96028 KB Output is correct
5 Correct 621 ms 96096 KB Output is correct
6 Correct 202 ms 5560 KB Output is correct
7 Correct 1135 ms 203056 KB Output is correct
8 Correct 1252 ms 203176 KB Output is correct
9 Correct 994 ms 203108 KB Output is correct
10 Correct 258 ms 27560 KB Output is correct
11 Correct 289 ms 38040 KB Output is correct
12 Correct 127 ms 4184 KB Output is correct
13 Correct 1791 ms 203064 KB Output is correct
14 Correct 1631 ms 203144 KB Output is correct
15 Correct 1197 ms 203172 KB Output is correct
16 Correct 790 ms 95532 KB Output is correct
17 Correct 764 ms 95512 KB Output is correct
18 Correct 233 ms 5496 KB Output is correct
19 Correct 1665 ms 203200 KB Output is correct
20 Correct 1643 ms 203208 KB Output is correct
21 Correct 1638 ms 203312 KB Output is correct
22 Correct 258 ms 27696 KB Output is correct
23 Correct 293 ms 37980 KB Output is correct
24 Correct 135 ms 4192 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 3086 ms 1188 KB Time limit exceeded
5 Halted 0 ms 0 KB -