oj.uz

답안 #752331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752331 2023-06-02T21:03:11 Z BidoTeima Examination (JOI19_examination) C++17
20 / 100
 395 ms 47880 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(0, l, r - 1, y, 0, n - 1, 0) + query(1, r, n - 1, z, 0, n - 1, 0)<<'\n';
        }
    }
    return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 47724 KB Output is correct
2 Correct 342 ms 47636 KB Output is correct
3 Correct 335 ms 47532 KB Output is correct
4 Correct 250 ms 47648 KB Output is correct
5 Correct 222 ms 47684 KB Output is correct
6 Correct 163 ms 47632 KB Output is correct
7 Correct 318 ms 47572 KB Output is correct
8 Correct 321 ms 47576 KB Output is correct
9 Correct 301 ms 47880 KB Output is correct
10 Correct 154 ms 47384 KB Output is correct
11 Correct 218 ms 47404 KB Output is correct
12 Correct 132 ms 47208 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 47724 KB Output is correct
2 Correct 342 ms 47636 KB Output is correct
3 Correct 335 ms 47532 KB Output is correct
4 Correct 250 ms 47648 KB Output is correct
5 Correct 222 ms 47684 KB Output is correct
6 Correct 163 ms 47632 KB Output is correct
7 Correct 318 ms 47572 KB Output is correct
8 Correct 321 ms 47576 KB Output is correct
9 Correct 301 ms 47880 KB Output is correct
10 Correct 154 ms 47384 KB Output is correct
11 Correct 218 ms 47404 KB Output is correct
12 Correct 132 ms 47208 KB Output is correct
13 Incorrect 395 ms 47564 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -