Submission #716199

#	Time	Username	Problem	Language	Result	Execution time	Memory
716199		TheSahib	Examination (JOI19_examination)	C++17	20 / 100	3089 ms	577528 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;
const int MAXVAL = (1 << 17) - 1;

struct SegTree1D{
    vector<int> tree, L, R;
    int nxt = 0;
    SegTree1D(){
        addNode();
    }
    int addNode(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
        return nxt++;
    }
    void update(int node, int l, int r, int pos, int val){
        int mid = 0;
        while(l != r){
            tree[node] += val;
            mid = (l + r) >> 1;
            if(pos <= mid){
                if(!L[node]) L[node] = addNode();
                node = L[node];
                r = mid;
            }
            else{
                if(!R[node]) R[node] = addNode();
                node = R[node];
                l = mid + 1;
            }
        }
        tree[node] += val;
    }

    int ask(int node, int l, int r, int ql, int qr){
        if(r < ql || qr < l) return 0;
        if(ql <= l && r <= qr) return tree[node];
        
        int ans = 0;
        int mid = (l + r) >> 1;
        if(L[node]) ans += ask(L[node], l, mid, ql, qr);
        if(R[node]) ans += ask(R[node], mid + 1, r, ql, qr);
        return ans;
    }
};

struct SegTree2D{
    SegTree1D tree[TREE_SIZE];
    int L[TREE_SIZE], R[TREE_SIZE];
    int nxt = 0;
 
    int addNode(){
        return nxt++;
    }
 
    SegTree2D(){
        addNode();
        memset(L, 0, sizeof(L));
        memset(R, 0, sizeof(R));
    }
    void update(int node, int l, int r, int ux, int uy, int val){
        int mid = 0;
        while(l != r){
            tree[node].update(0, 0, MAXVAL, ux, val);
            mid = (l + r) >> 1;
            if(uy <= mid){
                if(!L[node]) L[node] = addNode();
                node = L[node];
                r = mid;
            }
            else{
                if(!R[node]) R[node] = addNode();
                node = R[node];
                l = mid + 1;
            }
        }
        tree[node].update(0, 0, MAXVAL, ux, val);
    }
    int ask(int node, int l, int r, int x1, int x2, int y1, int y2){
        if(r < y1 || y2 < l) return 0;
        if(y1 <= l && r <= y2) return tree[node].ask(0, 0, MAXVAL, x1, x2);
        
        int ans = 0;
        int mid = (l + r) >> 1;
        if(L[node]) ans += ask(L[node], l, mid, x1, x2, y1, y2);
        if(R[node]) ans += ask(R[node], mid + 1, r, x1, x2, y1, y2);
        return ans;
    }
};


bool comp1(pii p1, pii p2){
    return (p1.first + p1.second) < (p2.first + p2.second);
}

bool comp2(array<int, 4>& a1, array<int, 4>& a2){
    return a1[2] < a2[2];
}

SegTree2D tree;

pii scores[MAX];
array<int, 4> querries[MAX];
int ans[MAX];

int main(){
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &scores[i].first, &scores[i].second);
        tree.update(0, 0, MAXVAL, scores[i].first, scores[i].second, 1);
    }
    sort(scores, scores + n, comp1);
    for (int i = 0; i < q; i++)
    {
        scanf("%d%d%d", &querries[i][0], &querries[i][1], &querries[i][2]);
        querries[i][3] = i;
    }
    sort(querries, querries + q, comp2);
    int last = 0;
    for (int i = 0; i < q; i++)
    {
        while(last < n && scores[last].first + scores[last].second < querries[i][2]){
            tree.update(0, 0, MAXVAL, scores[last].first, scores[last].second, -1);
            last++;
        }
        ans[querries[i][3]] = tree.ask(0, 0, MAXVAL, querries[i][0], MAX, querries[i][1], MAX);
    }
    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%d %d", &scores[i].first, &scores[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%d%d%d", &querries[i][0], &querries[i][1], &querries[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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