Submission #983163

#	Time	Username	Problem	Language	Result	Execution time	Memory
983163		PanosPask	Examination (JOI19_examination)	C++14	100 / 100	598 ms	19028 KiB

examination

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

struct BITree {
    int size;
    vector<int> tree;

    void init(int N) {
        size = N;
        tree.assign(size, 0);
    }

    void add(int i, int v) {
        for (int idx = i; idx < size; idx = idx | (idx + 1)) {
            tree[idx] += v;
        }
    }

    int get(int i) {
        int res = 0;
        for (int idx = i; idx >= 0; idx = (idx & (idx + 1)) - 1) {
            res += tree[idx];
        }

        return res;
    }
    int get(int l, int r) {
        return get(r - 1) - get(l - 1);
    }
    int rget(int i) {
        return get(i, size);
    }
};

const int STUDENT = 0;
const int QUERY = 1;

struct Event {
    int type;
    int x, y;
    int z;

    // For queries only
    int id = -1;
};

bool sumsort(const Event& a, const Event& b)
{
    if (a.z == b.z) {
        // We want to count a student that has grades equal to a query
        return a.type < b.type;
    }
    return a.z > b.z;
}
bool xsort(const Event& a, const Event& b)
{
    return a.x > b.x;
}

int N, Q;
vector<int> ycords;
vector<int> ans;
BITree b;

int yfind(int v)
{
    int pos = lower_bound(ycords.begin(), ycords.end(), v) - ycords.begin();
    return pos;
}

void add_student(int y, int v)
{
    int pos = yfind(y);
    b.add(pos, v);
}

void update_query(int y, int id)
{
    int pos = yfind(y);
    int res = b.rget(pos);

    ans[id] += res;
}

void cdq_dq(vector<Event>& events)
{
    if (events.size() <= 1) {
        return;
    }

    int mid = events.size() / 2;
    vector<Event> e1(mid), e2(events.size() - mid);

    for (int i = 0; i < mid; i++) {
        e1[i] = events[i];
    }
    for (int i = mid; i < events.size(); i++) {
        e2[i - mid] = events[i];
    }

    cdq_dq(e1);
    cdq_dq(e2);

    // Check how the STUDENTS of e1 affect the QUERIES of e2
    sort(e1.begin(), e1.end(), xsort);
    sort(e2.begin(), e2.end(), xsort);

    int curp = 0;
    for (int i = 0; i < e2.size(); i++) {
        if (e2[i].type == STUDENT) {
            continue;
        }

        while (curp < e1.size() && e1[curp].x >= e2[i].x) {
            if (e1[curp].type == STUDENT) {
                add_student(e1[curp].y, 1);
            }
            curp++;
        }

        update_query(e2[i].y, e2[i].id);
    }

    while (curp > 0) {
        if (e1[curp - 1].type == STUDENT) {
            add_student(e1[curp - 1].y, -1);
        }
        curp--;
    }
}

int main(void)
{
    scanf("%d %d", &N, &Q);
    vector<Event> initial(N + Q);
    ans.assign(Q, 0);

    for (int i = 0; i < N; i++) {
        int x, y;
        scanf("%d %d", &x, &y);

        initial[i].type = STUDENT;
        initial[i].x = x;
        initial[i].y = y;
        initial[i].z = x + y;
        initial[i].id = -1;

        ycords.pb(initial[i].y);
    }
    for (int i = 0; i < Q; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);

        initial[i + N].type = QUERY;
        initial[i + N].x = x;
        initial[i + N].y = y;
        initial[i + N].z = z;
        initial[i + N].id = i;

        ycords.pb(initial[i + N].y);
    }

    sort(ycords.begin(), ycords.end());
    ycords.resize(unique(ycords.begin(), ycords.end()) - ycords.begin());

    b.init(ycords.size());

    sort(initial.begin(), initial.end(), sumsort);
    cdq_dq(initial);

    for (int i = 0; i < Q; i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void cdq_dq(std::vector<Event>&)':
examination.cpp:99:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = mid; i < events.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~
examination.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < e2.size(); i++) {
      |                     ~~^~~~~~~~~~~
examination.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while (curp < e1.size() && e1[curp].x >= e2[i].x) {
      |                ~~~~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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