제출 #731685

#제출 시각아이디문제언어결과실행 시간메모리
731685TheSahibExamination (JOI19_examination)C++17
100 / 100
1890 ms211840 KiB
#include <bits/stdc++.h>
 
 
#define ll long long
#define pii pair<int, int>
 
using namespace std;
 
const int MAX = 1e5 + 5;
const int TREE_SIZE = MAX * 17 * 17;
const int MAXVAL = (1 << 17) - 1;

int tree1D[TREE_SIZE], L[TREE_SIZE], R[TREE_SIZE];
int nxt = MAX * 4;

void update1D(int node, int l, int r, int pos, int val){
    tree1D[node] += val;
    if(l == r) return;
    int mid = (l + r) / 2;
    if(pos <= mid){
        if(!L[node]) L[node] = ++nxt;
        update1D(L[node], l, mid, pos, val);
    }
    else{
        if(!R[node]) R[node] = ++nxt;
        update1D(R[node], mid + 1, r, pos, val);
    }
}

int ask1D(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l){
        return 0;
    }
    if(ql <= l && r <= qr){
        return tree1D[node];
    }
    int mid = (l + r) / 2;
    int ans = 0;

    if(L[node]) ans += ask1D(L[node], l, mid, ql, qr);
    if(R[node]) ans += ask1D(R[node], mid + 1, r, ql, qr);

    return ans;
}

void update(int node, int l, int r, int x, int y, int val){
    update1D(node, 0, MAXVAL, x, val);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(y <= mid){
        update(node * 2 + 1, l, mid, x, y, val);
    }
    else{
        update((node + 1) * 2, mid + 1, r, x, y, val);
    }
}

int ask(int node, int l, int r, int x1, int y1, int x2, int y2){
    if(y1 > r || y2 < l){
        return 0;
    }
    if(y1 <= l && r <= y2){
        return ask1D(node, 0, MAXVAL, x1, x2);
    }
    int mid = (l + r) / 2;
    return ask(node * 2 + 1, l, mid, x1, y1, x2, y2) + ask((node + 1) * 2, mid + 1, r, x1, y1, x2, y2);
}

bool comp(pii a, pii b){
    return a.first + a.second < b.first + b.second;
}
bool comp2(pii a, pii b){
    return a.second < b.second;
}

pii arr[MAX];
pii xSort[MAX];
pii ySort[MAX];
pii compress[MAX];
array<int, 4> q[MAX];
int ans[MAX];
int main(){
    int n, m; scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &arr[i].first, &arr[i].second);
        xSort[i] = arr[i];
        ySort[i] = arr[i];
    }
    
    sort(arr, arr + n, comp);
    sort(xSort, xSort + n);
    sort(ySort, ySort + n, comp2);

    for (int i = 0; i < n; i++)
    {
        compress[i] = {lower_bound(xSort, xSort + n, arr[i]) - xSort, 
                        lower_bound(ySort, ySort + n, arr[i], comp2) - ySort};
        update(0, 0, MAX, compress[i].first, compress[i].second, 1);
    }

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &q[i][1], &q[i][2], &q[i][0]);
        q[i][3] = i;
    }
    sort(q, q + m);
    int last = 0;
    for (int i = 0; i < m; i++)
    {
        while(last != n && arr[last].first + arr[last].second < q[i][0]){
            update(0, 0, MAX, compress[last].first, compress[last].second, -1);
            ++last;
        }
        int x = lower_bound(xSort, xSort + n, make_pair(q[i][1], -1)) - xSort;
        int y = lower_bound(ySort, ySort + n, make_pair(-1, q[i][2]), comp2) - ySort;
        ans[q[i][3]] = ask(0, 0, MAX, x, y, MAX, MAX);
    }
    for (int i = 0; i < m; i++)
    {
        cout << ans[i] << '\n';
    }
    
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:83:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d %d", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d %d %d", &q[i][1], &q[i][2], &q[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...