Submission #731681

#	Time	Username	Problem	Language	Result	Execution time	Memory
731681		TheSahib	Examination (JOI19_examination)	C++17	41 / 100	2179 ms	204076 KiB

examination

#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;
}

pii arr[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);
        update(0, 0, MAX, arr[i].first, arr[i].second, 1);
    }
    
    sort(arr, arr + n, comp);

    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, arr[last].first, arr[last].second, -1);
            ++last;
        }
        int x = q[i][1], y = q[i][2];
        ans[q[i][3]] = n - last;
        if(x != 0){
            ans[q[i][3]] -= ask(0, 0, MAX, 0, 0, x - 1, MAX);
        }
        if(y != 0){
            ans[q[i][3]] -= ask(0, 0, MAX, 0, 0, MAX, y - 1);
        }
        if(x != 0 && y != 0){
            ans[q[i][3]] += ask(0, 0, MAX, 0, 0, x - 1, y - 1);
        }
    }
    for (int i = 0; i < m; i++)
    {
        cout << ans[i] << '\n';
    }
    
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:77:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d %d", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d %d", &q[i][1], &q[i][2], &q[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 0 / 57