oj.uz

Submission #747626

# Submission time Handle Problem Language Result Execution time Memory
747626 2023-05-24T12:08:27 Z TahirAliyev Examination (JOI19_examination) C++17
41 / 100
 3000 ms 206216 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++)
    {
        cin >> 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; cin >> 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';
    }
}

Subtask #1
0 / 2.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1291 ms 205740 KB Output is correct
2 Correct 1295 ms 205772 KB Output is correct
3 Correct 1254 ms 205764 KB Output is correct
4 Correct 649 ms 97820 KB Output is correct
5 Correct 642 ms 97844 KB Output is correct
6 Correct 224 ms 6580 KB Output is correct
7 Correct 1159 ms 205632 KB Output is correct
8 Correct 1279 ms 205492 KB Output is correct
9 Correct 1053 ms 205484 KB Output is correct
10 Correct 307 ms 29280 KB Output is correct
11 Correct 342 ms 39784 KB Output is correct
12 Correct 173 ms 5164 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1291 ms 205740 KB Output is correct
2 Correct 1295 ms 205772 KB Output is correct
3 Correct 1254 ms 205764 KB Output is correct
4 Correct 649 ms 97820 KB Output is correct
5 Correct 642 ms 97844 KB Output is correct
6 Correct 224 ms 6580 KB Output is correct
7 Correct 1159 ms 205632 KB Output is correct
8 Correct 1279 ms 205492 KB Output is correct
9 Correct 1053 ms 205484 KB Output is correct
10 Correct 307 ms 29280 KB Output is correct
11 Correct 342 ms 39784 KB Output is correct
12 Correct 173 ms 5164 KB Output is correct
13 Correct 1839 ms 205932 KB Output is correct
14 Correct 1655 ms 206048 KB Output is correct
15 Correct 1377 ms 205552 KB Output is correct
16 Correct 867 ms 97688 KB Output is correct
17 Correct 823 ms 97668 KB Output is correct
18 Correct 266 ms 6472 KB Output is correct
19 Correct 1787 ms 206104 KB Output is correct
20 Correct 1736 ms 206088 KB Output is correct
21 Correct 1766 ms 206216 KB Output is correct
22 Correct 306 ms 29364 KB Output is correct
23 Correct 341 ms 39692 KB Output is correct
24 Correct 166 ms 5204 KB Output is correct

Subtask #4
0 / 57.0

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