Submission #786749

#	Time	Username	Problem	Language	Result	Execution time	Memory
786749		PanosPask	Examination (JOI19_examination)	C++14	100 / 100	620 ms	19412 KiB

examination

#include <bits/stdc++.h>

using namespace std;

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

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 x = i; x < size; x = x | (x + 1))
            tree[x] += v;
    }

    int get(int i) {
        int res = 0;
        for (int x = i; x >= 0; x = (x & (x + 1)) - 1)
            res += tree[x];
        return res;
    }
    int get(int l, int r) {
        int a = get(r - 1);
        int b = get(l - 1);

        return a - b;
    }
    int rget(int i) {
        return get(i, size);
    }
};

struct Event {
    int type;
    int x, y;
    int z;
    int id;
};
bool sumsort(const Event& a, const Event& b)
{
    if (a.z == b.z)
        return a.type < b.type;
    return a.z > b.z;
}
bool xsort(const Event& a, const Event& b)
{
    return a.x > b.x;
}

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

int find(int v)
{
    return lower_bound(ycords.begin(), ycords.end(), v) - ycords.begin();
}

void add_student(const Event& s, int mul = 1)
{
    if (s.type == QUERY)
        return;

    b.add(find(s.y), 1 * mul);
}
void make_query(const Event& s)
{
    if (s.type == STUDENT)
        return;

    ans[s.id] += b.rget(find(s.y));
}

void cdq_dc(vector<Event>& events)
{
    if (events.size() == 1) {
        // Nothing can be done
        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_dc(e1);
    cdq_dc(e2);

    sort(e1.begin(), e1.end(), xsort);
    sort(e2.begin(), e2.end(), xsort);

    int to_add = 0;
    for (auto e : e2) {
        while (to_add < e1.size() && e1[to_add].x >= e.x) {
            add_student(e1[to_add]);
            to_add++;
        }

        make_query(e);
    }

    while (to_add) {
        to_add--;
        add_student(e1[to_add], -1);
    }
}

int main(void)
{
    scanf("%d %d", &N, &Q);

    ans.resize(Q);

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

        initial.push_back({STUDENT, x, y, x + y, -1});
    }
    for (int i = 0; i < Q; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        ycords.push_back(y);

        initial.push_back({QUERY, x, y, z, i});
    }
    sort(initial.begin(), initial.end(), sumsort);
    sort(ycords.begin(), ycords.end());
    ycords.resize(unique(ycords.begin(), ycords.end()) - ycords.begin());

    b.init(ycords.size());
    cdq_dc(initial);

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

    return 0;
}

Compilation message (stderr)

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

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