oj.uz

Submission #836910

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -