oj.uz

Submission #836917

# Submission time Handle Problem Language Result Execution time Memory
836917 2023-08-24T17:11:18 Z borisAngelov Examination (JOI19_examination) C++17
100 / 100
 540 ms 35852 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;
    bool is_query;
    int query_idx;

    element()
    {

    }

    element(int _x, int _y, int _z, bool _is_query, int _query_idx)
    {
        x = _x;
        y = _y;
        z = _z;
        is_query = _is_query;
        query_idx = _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<element> active;

    for (int i = l; i <= mid; ++i)
    {
        if (a[i].is_query == false)
        {
            active.push_back(element(0, a[i].y, a[i].z, false, 0));
        }
    }

    for (int i = mid + 1; i <= r; ++i)
    {
        if (a[i].is_query == true)
        {
            active.push_back(element(0, a[i].y, a[i].z, true, a[i].query_idx));
        }
    }

    sort(active.begin(), active.end(), [&](element fr, element sc)
    {
        return make_pair(fr.y, -fr.is_query) > make_pair(sc.y, -sc.is_query);
    });

    vector<int> pos_to_clear;

    for (int i = 0; i < active.size(); ++i)
    {
        if (active[i].is_query == false)
        {
            bit.update(active[i].z, +1);
            pos_to_clear.push_back(active[i].z);
        }
        else
        {
            answers[active[i].query_idx] += (bit.query(max_number) - bit.query(active[i].z - 1));
        }
    }

    for (int i = 0; i < pos_to_clear.size(); ++i)
    {
        bit.update(pos_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

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

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 1364 KB Output is correct
8 Correct 9 ms 1364 KB Output is correct
9 Correct 10 ms 1364 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct
11 Correct 8 ms 1108 KB Output is correct
12 Correct 6 ms 716 KB Output is correct
13 Correct 10 ms 1264 KB Output is correct
14 Correct 9 ms 1236 KB Output is correct
15 Correct 9 ms 1228 KB Output is correct
16 Correct 7 ms 1016 KB Output is correct
17 Correct 8 ms 1056 KB Output is correct
18 Correct 5 ms 652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 13304 KB Output is correct
2 Correct 282 ms 13244 KB Output is correct
3 Correct 280 ms 13196 KB Output is correct
4 Correct 245 ms 11216 KB Output is correct
5 Correct 249 ms 11228 KB Output is correct
6 Correct 220 ms 11256 KB Output is correct
7 Correct 270 ms 16832 KB Output is correct
8 Correct 250 ms 13192 KB Output is correct
9 Correct 257 ms 16636 KB Output is correct
10 Correct 216 ms 13436 KB Output is correct
11 Correct 196 ms 11272 KB Output is correct
12 Correct 205 ms 10520 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 13304 KB Output is correct
2 Correct 282 ms 13244 KB Output is correct
3 Correct 280 ms 13196 KB Output is correct
4 Correct 245 ms 11216 KB Output is correct
5 Correct 249 ms 11228 KB Output is correct
6 Correct 220 ms 11256 KB Output is correct
7 Correct 270 ms 16832 KB Output is correct
8 Correct 250 ms 13192 KB Output is correct
9 Correct 257 ms 16636 KB Output is correct
10 Correct 216 ms 13436 KB Output is correct
11 Correct 196 ms 11272 KB Output is correct
12 Correct 205 ms 10520 KB Output is correct
13 Correct 293 ms 12976 KB Output is correct
14 Correct 294 ms 16252 KB Output is correct
15 Correct 265 ms 15708 KB Output is correct
16 Correct 246 ms 13376 KB Output is correct
17 Correct 247 ms 13484 KB Output is correct
18 Correct 231 ms 12256 KB Output is correct
19 Correct 290 ms 15816 KB Output is correct
20 Correct 290 ms 16596 KB Output is correct
21 Correct 291 ms 17148 KB Output is correct
22 Correct 218 ms 15292 KB Output is correct
23 Correct 206 ms 13016 KB Output is correct
24 Correct 195 ms 11484 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 1364 KB Output is correct
8 Correct 9 ms 1364 KB Output is correct
9 Correct 10 ms 1364 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct
11 Correct 8 ms 1108 KB Output is correct
12 Correct 6 ms 716 KB Output is correct
13 Correct 10 ms 1264 KB Output is correct
14 Correct 9 ms 1236 KB Output is correct
15 Correct 9 ms 1228 KB Output is correct
16 Correct 7 ms 1016 KB Output is correct
17 Correct 8 ms 1056 KB Output is correct
18 Correct 5 ms 652 KB Output is correct
19 Correct 268 ms 13304 KB Output is correct
20 Correct 282 ms 13244 KB Output is correct
21 Correct 280 ms 13196 KB Output is correct
22 Correct 245 ms 11216 KB Output is correct
23 Correct 249 ms 11228 KB Output is correct
24 Correct 220 ms 11256 KB Output is correct
25 Correct 270 ms 16832 KB Output is correct
26 Correct 250 ms 13192 KB Output is correct
27 Correct 257 ms 16636 KB Output is correct
28 Correct 216 ms 13436 KB Output is correct
29 Correct 196 ms 11272 KB Output is correct
30 Correct 205 ms 10520 KB Output is correct
31 Correct 293 ms 12976 KB Output is correct
32 Correct 294 ms 16252 KB Output is correct
33 Correct 265 ms 15708 KB Output is correct
34 Correct 246 ms 13376 KB Output is correct
35 Correct 247 ms 13484 KB Output is correct
36 Correct 231 ms 12256 KB Output is correct
37 Correct 290 ms 15816 KB Output is correct
38 Correct 290 ms 16596 KB Output is correct
39 Correct 291 ms 17148 KB Output is correct
40 Correct 218 ms 15292 KB Output is correct
41 Correct 206 ms 13016 KB Output is correct
42 Correct 195 ms 11484 KB Output is correct
43 Correct 515 ms 35840 KB Output is correct
44 Correct 479 ms 35852 KB Output is correct
45 Correct 540 ms 35796 KB Output is correct
46 Correct 385 ms 29108 KB Output is correct
47 Correct 348 ms 29116 KB Output is correct
48 Correct 229 ms 12072 KB Output is correct
49 Correct 466 ms 35576 KB Output is correct
50 Correct 483 ms 35756 KB Output is correct
51 Correct 453 ms 35600 KB Output is correct
52 Correct 292 ms 21932 KB Output is correct
53 Correct 223 ms 18596 KB Output is correct