Submission #201870

#	Time	Username	Problem	Language	Result	Execution time	Memory
201870		blue	Examination (JOI19_examination)	C++17	100 / 100	2496 ms	121720 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int N, Q;

struct event
{
    int x, y, z;
    int i;
};

event* E;

bool xsort(event a, event b)
{
    return a.x < b.x;
}

bool zsort(event a, event b)
{
    if(a.z == b.z) return a.i > b.i;
    return a.z > b.z;
}

map<int, int>* Ys = new map<int, int>[200001];

int main()
{
    cin >> N >> Q;

    E = new event[N+Q];
    for(int i = 0; i < N; i++)
    {
        cin >> E[i].x >> E[i].y;
        E[i].z = E[i].x + E[i].y;
        E[i].x *= -1;
        E[i].y *= -1;
        E[i].i = i+1;
    }
    for(int i = 0; i < Q; i++)
    {
        cin >> E[N+i].x >> E[N+i].y >> E[N+i].z;
        E[N+i].x *= -1;
        E[N+i].y *= -1;
        E[N+i].i = -(i+1);
    }

    sort(E, E+N+Q, xsort);
    int p = E[0].x, q;
    E[0].x = 1;
    for(int i = 1; i < N+Q; i++)
    {
        q = E[i].x;
        E[i].x = E[i-1].x + (p != q);
        p = q;
    }
    for(int i = 0; i < N+Q; i++)
    {
        if(E[i].i > 0)
            for(int j = E[i].x; j <= 200000; j += j&-j) Ys[j][E[i].y] = 0;
        else
            for(int j = E[i].x; j >= 1; j -= j&-j) Ys[j][E[i].y] = 0;

    }

    for(int i = 1; i <= 200000; i++)
    {
        int q = 0;
        for(auto& ys: Ys[i])
        {
            q++;
            ys.second = q;
        }
    }

    int* BIT[200001];
    for(int i = 1; i <= 200000; i++)
    {
        BIT[i] = new int[Ys[i].size() + 1];
        for(int j = 1; j <= Ys[i].size(); j++) BIT[i][j] = 0;
    }

    int res[Q+1];
    sort(E, E+N+Q, zsort);
    for(int i = 0; i < N+Q; i++)
    {
        if(E[i].i > 0)
        {
            for(int j = E[i].x; j <= 200000; j += j&-j)
                for(int k = Ys[ j ][ E[i].y ]; k <= Ys[ j ].size(); k += k&-k)
                    BIT[j][k]++;
        }
        else
        {
            res[-(E[i].i)] = 0;
            for(int j = E[i].x; j >= 1; j -= j&-j)
                for(int k = Ys[ j ][ E[i].y ]; k >= 1; k -= k&-k)
                    res[-(E[i].i)] += BIT[j][k];
        }
    }
    for(int i = 1; i <= Q; i++) cout << res[i] << '\n';
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:83:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j <= Ys[i].size(); j++) BIT[i][j] = 0;
                        ~~^~~~~~~~~~~~~~~
examination.cpp:93:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k = Ys[ j ][ E[i].y ]; k <= Ys[ j ].size(); k += k&-k)
                                                ~~^~~~~~~~~~~~~~~~~

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