Submission #355473

#	Time	Username	Problem	Language	Result	Execution time	Memory
355473		parsabahrami	Examination (JOI19_examination)	C++17	100 / 100	701 ms	47356 KiB

examination

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10;
vector<int> vec[N], F[N], comp = {(int) -1e9};
pii A[N]; int n, q, R[N], id[N], X[N], Y[N], Z[N];

void init(int x, int y) {
    for (; x < N; x += x & -x) {
        vec[x].push_back(y);
    }
}

void upd(int r, int _c) {
    for (; r < N; r += r & -r) {
        int c = lower_bound(vec[r].begin(), vec[r].end(), _c) - vec[r].begin();
        for (; c < SZ(F[r]); c += c & -c) F[r][c]++;
    }
}

int get(int r, int _c) {
    int ret = 0;
    for (; r; r -= r & -r) {
        int c = upper_bound(vec[r].begin(), vec[r].end(), _c) - vec[r].begin() - 1;
        for (; c; c -= c & -c) ret += F[r][c];
    }
    return ret;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d%d", &A[i].F, &A[i].S), comp.push_back(-A[i].F);
    sort(A + 1, A + n + 1, [&] (pii a, pii b) { return a.F + a.S > b.F + b.S; });
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &X[i], &Y[i], &Z[i]); id[i] = i;
        comp.push_back(-X[i]);
    }
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    sort(id + 1, id + q + 1, [&] (int i, int j) { return Z[i] > Z[j]; });
    for (int i = 1; i <= n; i++) {
        init(lower_bound(comp.begin(), comp.end(), -A[i].F) - comp.begin(), -A[i].S);
    }
    for (int i = 0; i < N; i++) {
        vec[i].push_back(-1e9); vec[i].push_back(0);
        sort(vec[i].begin(), vec[i].end());
        vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
        while (SZ(F[i]) < SZ(vec[i]) + 5) F[i].push_back(0);
    }
    int ptr = 1;
    for (int _ = 1; _ <= q; _++) {
        int i = id[_];
        while (ptr <= n && A[ptr].F + A[ptr].S >= Z[i]) {
            upd(lower_bound(comp.begin(), comp.end(), -A[ptr].F) - comp.begin(), -A[ptr].S);
            ptr++;
        }
        R[i] = get(lower_bound(comp.begin(), comp.end(), -X[i]) - comp.begin(), -Y[i]);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", R[i]);
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:41:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     for (int i = 1; i <= n; i++) scanf("%d%d", &A[i].F, &A[i].S), comp.push_back(-A[i].F);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         scanf("%d%d%d", &X[i], &Y[i], &Z[i]); id[i] = i;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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