oj.uz

답안 #201868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201868 2020-02-12T13:14:10 Z blue Examination (JOI19_examination) C++17
2 / 100
 3000 ms 173492 KB 
#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:80: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:90: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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 17528 KB Output is correct
2 Correct 20 ms 17528 KB Output is correct
3 Correct 19 ms 17528 KB Output is correct
4 Correct 19 ms 17528 KB Output is correct
5 Correct 20 ms 17532 KB Output is correct
6 Correct 20 ms 17532 KB Output is correct
7 Correct 60 ms 22904 KB Output is correct
8 Correct 61 ms 23032 KB Output is correct
9 Correct 60 ms 22904 KB Output is correct
10 Correct 34 ms 18680 KB Output is correct
11 Correct 56 ms 23032 KB Output is correct
12 Correct 27 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 60 ms 22904 KB Output is correct
16 Correct 47 ms 23032 KB Output is correct
17 Correct 30 ms 18168 KB Output is correct
18 Correct 25 ms 17680 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3038 ms 173492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3038 ms 173492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 17528 KB Output is correct
2 Correct 20 ms 17528 KB Output is correct
3 Correct 19 ms 17528 KB Output is correct
4 Correct 19 ms 17528 KB Output is correct
5 Correct 20 ms 17532 KB Output is correct
6 Correct 20 ms 17532 KB Output is correct
7 Correct 60 ms 22904 KB Output is correct
8 Correct 61 ms 23032 KB Output is correct
9 Correct 60 ms 22904 KB Output is correct
10 Correct 34 ms 18680 KB Output is correct
11 Correct 56 ms 23032 KB Output is correct
12 Correct 27 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 60 ms 22904 KB Output is correct
16 Correct 47 ms 23032 KB Output is correct
17 Correct 30 ms 18168 KB Output is correct
18 Correct 25 ms 17680 KB Output is correct
19 Execution timed out 3038 ms 173492 KB Time limit exceeded
20 Halted 0 ms 0 KB -