oj.uz

Submission #752332

# Submission time Handle Problem Language Result Execution time Memory
752332 2023-06-02T21:07:43 Z BidoTeima Examination (JOI19_examination) C++17
20 / 100
 437 ms 47760 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 >= x - 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 Correct 10 ms 19028 KB Output is correct
2 Incorrect 12 ms 19120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 47632 KB Output is correct
2 Correct 388 ms 47660 KB Output is correct
3 Correct 338 ms 47760 KB Output is correct
4 Correct 252 ms 47592 KB Output is correct
5 Correct 231 ms 47640 KB Output is correct
6 Correct 168 ms 47748 KB Output is correct
7 Correct 318 ms 47564 KB Output is correct
8 Correct 337 ms 47628 KB Output is correct
9 Correct 305 ms 47660 KB Output is correct
10 Correct 165 ms 47456 KB Output is correct
11 Correct 210 ms 47472 KB Output is correct
12 Correct 127 ms 47228 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 47632 KB Output is correct
2 Correct 388 ms 47660 KB Output is correct
3 Correct 338 ms 47760 KB Output is correct
4 Correct 252 ms 47592 KB Output is correct
5 Correct 231 ms 47640 KB Output is correct
6 Correct 168 ms 47748 KB Output is correct
7 Correct 318 ms 47564 KB Output is correct
8 Correct 337 ms 47628 KB Output is correct
9 Correct 305 ms 47660 KB Output is correct
10 Correct 165 ms 47456 KB Output is correct
11 Correct 210 ms 47472 KB Output is correct
12 Correct 127 ms 47228 KB Output is correct
13 Incorrect 437 ms 47528 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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