oj.uz

Submission #752330

# Submission time Handle Problem Language Result Execution time Memory
752330 2023-06-02T20:57:38 Z BidoTeima Examination (JOI19_examination) C++17
20 / 100
 415 ms 50536 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;
                    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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 47692 KB Output is correct
2 Correct 344 ms 50160 KB Output is correct
3 Correct 346 ms 50200 KB Output is correct
4 Correct 251 ms 49376 KB Output is correct
5 Correct 228 ms 49304 KB Output is correct
6 Correct 165 ms 48796 KB Output is correct
7 Correct 324 ms 50076 KB Output is correct
8 Correct 315 ms 50012 KB Output is correct
9 Correct 292 ms 49988 KB Output is correct
10 Correct 153 ms 49248 KB Output is correct
11 Correct 209 ms 49176 KB Output is correct
12 Correct 130 ms 48196 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 47692 KB Output is correct
2 Correct 344 ms 50160 KB Output is correct
3 Correct 346 ms 50200 KB Output is correct
4 Correct 251 ms 49376 KB Output is correct
5 Correct 228 ms 49304 KB Output is correct
6 Correct 165 ms 48796 KB Output is correct
7 Correct 324 ms 50076 KB Output is correct
8 Correct 315 ms 50012 KB Output is correct
9 Correct 292 ms 49988 KB Output is correct
10 Correct 153 ms 49248 KB Output is correct
11 Correct 209 ms 49176 KB Output is correct
12 Correct 130 ms 48196 KB Output is correct
13 Incorrect 415 ms 50536 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 -