oj.uz

답안 #836910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836910 2023-08-24T17:04:16 Z borisAngelov Examination (JOI19_examination) C++17
20 / 100
 204 ms 14396 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 600005;
const int max_number = 600000;

int n, q;

struct element
{
    int x;
    int y;
    int z;
    int is_query;
    int query_idx;
};

element a[maxn];

void compress()
{
    vector<int> to_sort;
    unordered_map<int, int> compressed;
    int curr_value = 0;

    for (int i = 1; i <= n + q; ++i)
    {
        to_sort.push_back(a[i].x);
        to_sort.push_back(a[i].y);
        to_sort.push_back(a[i].z);
    }

    sort(to_sort.begin(), to_sort.end());

    for (int i = 0; i < to_sort.size(); ++i)
    {
        if (i == 0 || to_sort[i] != to_sort[i - 1])
        {
            compressed[to_sort[i]] = ++curr_value;
        }
    }

    for (int i = 1; i <= n + q; ++i)
    {
        a[i].x = compressed[a[i].x];
        a[i].y = compressed[a[i].y];
        a[i].z = compressed[a[i].z];
    }
}

int answers[maxn];

struct fenwick_tree
{
    int tree[maxn];

    void update(int pos, int delta)
    {
        for (int i = pos; i <= max_number; i += (i & (-i)))
        {
            tree[i] += delta;
        }
    }

    int query(int pos)
    {
        int result = 0;

        for (int i = pos; i >= 1; i -= (i & (-i)))
        {
            result += tree[i];
        }

        return result;
    }
};

fenwick_tree bit;

void divide_and_conquer(int l, int r)
{
    if (l == r)
    {
        return;
    }

    int mid = (l + r) / 2;

    vector<int> to_clear;

    for (int i = l; i <= mid; ++i)
    {
        if (a[i].is_query == false)
        {
            to_clear.push_back(a[i].y);
            bit.update(a[i].y, +1);
        }
    }

    for (int i = mid + 1; i <= r; ++i)
    {
        if (a[i].is_query == true)
        {
            answers[a[i].query_idx] += (bit.query(max_number) - bit.query(a[i].y - 1));
        }
    }

    for (int i = 0; i < to_clear.size(); ++i)
    {
        bit.update(to_clear[i], -1);
    }

    divide_and_conquer(l, mid);
    divide_and_conquer(mid + 1, r);
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].x >> a[i].y;
        a[i].z = a[i].x + a[i].y;
    }

    for (int i = 1; i <= q; ++i)
    {
        cin >> a[i + n].x >> a[i + n].y >> a[i + n].z;
        a[i + n].is_query = true;
        a[i + n].query_idx = i;
    }

    compress();

    sort(a + 1, a + n + q + 1, [&](element fr, element sc)
    {
        return make_pair(fr.x, -fr.is_query) > make_pair(sc.x, -sc.is_query);
    });

    divide_and_conquer(1, n + q);

    for (int i = 1; i <= q; ++i)
    {
        cout << answers[i] << "\n";
    }

    return 0;
}

/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 0
10 10 0
60 60 0
0 100 0
*/

Compilation message

examination.cpp: In function 'void compress()':
examination.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < to_sort.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void divide_and_conquer(int, int)':
examination.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < to_clear.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 14316 KB Output is correct
2 Correct 189 ms 14396 KB Output is correct
3 Correct 188 ms 14348 KB Output is correct
4 Correct 201 ms 12708 KB Output is correct
5 Correct 157 ms 12704 KB Output is correct
6 Correct 170 ms 8480 KB Output is correct
7 Correct 172 ms 12088 KB Output is correct
8 Correct 195 ms 12136 KB Output is correct
9 Correct 181 ms 11888 KB Output is correct
10 Correct 140 ms 11232 KB Output is correct
11 Correct 196 ms 11232 KB Output is correct
12 Correct 152 ms 8444 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 14316 KB Output is correct
2 Correct 189 ms 14396 KB Output is correct
3 Correct 188 ms 14348 KB Output is correct
4 Correct 201 ms 12708 KB Output is correct
5 Correct 157 ms 12704 KB Output is correct
6 Correct 170 ms 8480 KB Output is correct
7 Correct 172 ms 12088 KB Output is correct
8 Correct 195 ms 12136 KB Output is correct
9 Correct 181 ms 11888 KB Output is correct
10 Correct 140 ms 11232 KB Output is correct
11 Correct 196 ms 11232 KB Output is correct
12 Correct 152 ms 8444 KB Output is correct
13 Incorrect 204 ms 12984 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -