oj.uz

Submission #752333

# Submission time Handle Problem Language Result Execution time Memory
752333 2023-06-02T21:19:44 Z BidoTeima Examination (JOI19_examination) C++17
20 / 100
 417 ms 47840 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 3;
vector<int> st[2][4 * N];
int a[2][N];
void build(bool b, int l, int r, int node){
    if(l == r){
        st[b][node] = {a[b][l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(b, l, mid, 2 * node + 1);
    build(b, mid + 1, r, 2 * node + 2); 
    for(int x : st[b][2 * node + 1])st[b][node].push_back(x);
    for(int x : st[b][2 * node + 2])st[b][node].push_back(x);
    sort(st[b][node].begin(),st[b][node].end());
    return;
}
int query(bool b, int ql, int qr, int x, int l, int r, int node){
    if(l > r)
        return 0;
    if(ql <= l && r <= qr){
        return st[b][node].end() - lower_bound(st[b][node].begin(), st[b][node].end(), x);
    }
    if(r < ql || l > qr){
        return 0;
    }
    int mid = (l + r) >> 1;
    return query(b, ql, qr, x, l, mid, 2 * node + 1) + 
            query(b, ql, qr, x, mid + 1, r, 2 * node + 2);
}
int main()
{ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    int n,q;
    cin>>n>>q;
    pair<int,int>arr[n];
    for(int i = 0; i < n; i++){
        cin>>arr[i].first>>arr[i].second;
    }
    sort(arr,arr+n);
    for(int i = 0; i < n; i++){
        a[0][i] = arr[i].second;
        a[1][i] = arr[i].first + arr[i].second;
    }
    build(0,0,n-1,0);
    build(1,0,n-1,0);
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        int l = lower_bound(arr, arr+n, make_pair(x, 0)) - arr;
        if(x + y >= z){
            //[l,n-1]
            cout<<query(0, l, n - 1, y, 0, n - 1, 0)<<'\n';
        } else{
            int r = n;
            int lo = l, hi = n - 1, mid;
            while(lo <= hi){
                mid = (lo + hi) >> 1;
                if(y >= z - a[0][mid]){
                    r = mid;
                    lo = mid + 1;
                } else{
                    hi = mid - 1;
                }
            }
            cout<<query(1, l, r - 1, z, 0, n - 1, 0) + query(0, r, n - 1, y, 0, n - 1, 0)<<'\n';
        }
    }
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 47632 KB Output is correct
2 Correct 372 ms 47640 KB Output is correct
3 Correct 338 ms 47556 KB Output is correct
4 Correct 264 ms 47572 KB Output is correct
5 Correct 248 ms 47608 KB Output is correct
6 Correct 167 ms 47544 KB Output is correct
7 Correct 363 ms 47616 KB Output is correct
8 Correct 314 ms 47640 KB Output is correct
9 Correct 342 ms 47840 KB Output is correct
10 Correct 163 ms 47396 KB Output is correct
11 Correct 222 ms 47456 KB Output is correct
12 Correct 134 ms 47300 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 47632 KB Output is correct
2 Correct 372 ms 47640 KB Output is correct
3 Correct 338 ms 47556 KB Output is correct
4 Correct 264 ms 47572 KB Output is correct
5 Correct 248 ms 47608 KB Output is correct
6 Correct 167 ms 47544 KB Output is correct
7 Correct 363 ms 47616 KB Output is correct
8 Correct 314 ms 47640 KB Output is correct
9 Correct 342 ms 47840 KB Output is correct
10 Correct 163 ms 47396 KB Output is correct
11 Correct 222 ms 47456 KB Output is correct
12 Correct 134 ms 47300 KB Output is correct
13 Incorrect 417 ms 47748 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -