oj.uz

Submission #752329

# Submission time Handle Problem Language Result Execution time Memory
752329 2023-06-02T20:32:37 Z BidoTeima Examination (JOI19_examination) C++17
0 / 100
 126 ms 23316 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][node]};
        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;
    }
    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 >= x - a[0][mid]){
                    r = mid;
                    hi = mid - 1;
                } else{
                    lo = 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
0 / 20.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 23316 KB Output isn't correct
2 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 -