oj.uz

Submission #201869

# Submission time Handle Problem Language Result Execution time Memory
201869 2020-02-12T13:14:34 Z blue Examination (JOI19_examination) C++17
2 / 100
 3000 ms 171256 KB 
//FIXME

#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++)
    {
        for(int j = E[i].x; j <= 200000; j += j&-j) Ys[j][E[i].y] = 0;
        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

examination.cpp: In function 'int main()':
examination.cpp:82: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:92: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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 17528 KB Output is correct
2 Correct 19 ms 17528 KB Output is correct
3 Correct 19 ms 17588 KB Output is correct
4 Correct 19 ms 17528 KB Output is correct
5 Correct 19 ms 17528 KB Output is correct
6 Correct 19 ms 17528 KB Output is correct
7 Correct 60 ms 22904 KB Output is correct
8 Correct 64 ms 22904 KB Output is correct
9 Correct 59 ms 22904 KB Output is correct
10 Correct 33 ms 18680 KB Output is correct
11 Correct 51 ms 23032 KB Output is correct
12 Correct 26 ms 17656 KB Output is correct
13 Correct 58 ms 22904 KB Output is correct
14 Correct 60 ms 22904 KB Output is correct
15 Correct 59 ms 22908 KB Output is correct
16 Correct 47 ms 23032 KB Output is correct
17 Correct 30 ms 18172 KB Output is correct
18 Correct 25 ms 17656 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3097 ms 171256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3097 ms 171256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 17528 KB Output is correct
2 Correct 19 ms 17528 KB Output is correct
3 Correct 19 ms 17588 KB Output is correct
4 Correct 19 ms 17528 KB Output is correct
5 Correct 19 ms 17528 KB Output is correct
6 Correct 19 ms 17528 KB Output is correct
7 Correct 60 ms 22904 KB Output is correct
8 Correct 64 ms 22904 KB Output is correct
9 Correct 59 ms 22904 KB Output is correct
10 Correct 33 ms 18680 KB Output is correct
11 Correct 51 ms 23032 KB Output is correct
12 Correct 26 ms 17656 KB Output is correct
13 Correct 58 ms 22904 KB Output is correct
14 Correct 60 ms 22904 KB Output is correct
15 Correct 59 ms 22908 KB Output is correct
16 Correct 47 ms 23032 KB Output is correct
17 Correct 30 ms 18172 KB Output is correct
18 Correct 25 ms 17656 KB Output is correct
19 Execution timed out 3097 ms 171256 KB Time limit exceeded
20 Halted 0 ms 0 KB -