oj.uz

Submission #907742

# Submission time Handle Problem Language Result Execution time Memory
907742 2024-01-16T03:59:04 Z trMatherz Examination (JOI19_examination) C++17
100 / 100
 645 ms 49140 KB 
#include <bits/stdc++.h>
using namespace std;

struct OfflineBit2d
{
    vector<vector<int64_t>> c, t;
    bool b;

    OfflineBit2d(size_t n)
    {
        b = 0;
        c = vector<vector<int64_t>>(n);
        t = vector<vector<int64_t>>(n);
    }

    void initialize()
    {
        b = 1;
        for (size_t i = 0; i < c.size(); i++)
        {
            sort(c[i].begin(), c[i].end());
            c[i].resize(unique(c[i].begin(), c[i].end()) - c[i].begin());
            t[i] = vector<int64_t>(c[i].size(), 0);
        }
    }

    void increment(int64_t i, int64_t j)
    {
        i++, j++;
        while (i <= t.size())
        {
            if (!b)
                c[i - 1].push_back(j);
            else
            {
                int64_t k = upper_bound(c[i - 1].begin(), c[i - 1].end(), j) -
                            c[i - 1].begin();
                while (k <= c[i - 1].size())
                {
                    t[i - 1][k - 1]++;
                    k += k & -k;
                }
            }
            i += i & -i;
        }
    }

    int64_t prefix_sum(size_t i, size_t j)
    {
        int64_t x = 0;
        i++, j++;

        while (i)
        {
            int64_t k = upper_bound(c[i - 1].begin(), c[i - 1].end(), j) - c[i - 1].begin();
            while (k)
            {
                x += t[i - 1][k - 1];
                k -= k & -k;
            }
            i -= i & -i;
        }
        return x;
    }

    int64_t range_sum(size_t i1, size_t i2, size_t j1, size_t j2)
    {
        int64_t x = prefix_sum(i2, j2);
        if (i1)
            x -= prefix_sum(i1 - 1, j2);
        if (j1)
            x -= prefix_sum(i2, j1 - 1);
        if (i1 && j1)
            x += prefix_sum(i1 - 1, j1 - 1);
        return x;
    }
};

struct Event
{
    int64_t t, x, y;
    size_t i;
    bool student;

    bool operator<(Event const &e) const
    {
        if (t == e.t)
            return student && !e.student;
        return t > e.t;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, q;
    cin >> n >> q;

    vector<Event> events;
    vector<int64_t> xcoords;

    for (size_t i = 0; i < n; i++)
    {
        int64_t x, y;
        cin >> x >> y;
        xcoords.push_back(x);
        events.push_back({x + y, x, y, SIZE_MAX, 1});
    }

    for (size_t i = 0; i < q; i++)
    {
        int64_t x, y, z;
        cin >> x >> y >> z;
        xcoords.push_back(x);
        events.push_back({z, x, y, i, 0});
    }

    sort(events.begin(), events.end());
    sort(xcoords.begin(), xcoords.end());
    xcoords.resize(unique(xcoords.begin(), xcoords.end()) - xcoords.begin());
    OfflineBit2d tree(xcoords.size());

    vector<int64_t> ans(q, 0);

    for (auto const &[t, x, y, i, student] : events)
        if (student)
            tree.increment(lower_bound(xcoords.begin(), xcoords.end(), x) - xcoords.begin(), y);
    tree.initialize();
    for (auto const &[t, x, y, i, student] : events)
    {
        if (student)
            tree.increment(lower_bound(xcoords.begin(), xcoords.end(), x) - xcoords.begin(), y);
        else
            ans[i] = tree.range_sum(
                lower_bound(xcoords.begin(), xcoords.end(), x) - xcoords.begin(),
                xcoords.size() - 1, y, 2000000000);
    }

    for (auto const &a : ans)
        cout << a << '\n';
}

Compilation message

examination.cpp: In member function 'void OfflineBit2d::increment(int64_t, int64_t)':
examination.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
examination.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 while (k <= c[i - 1].size())
      |                        ~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 9 ms 1720 KB Output is correct
8 Correct 8 ms 1716 KB Output is correct
9 Correct 8 ms 1720 KB Output is correct
10 Correct 5 ms 1460 KB Output is correct
11 Correct 4 ms 952 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 8 ms 1720 KB Output is correct
14 Correct 8 ms 1720 KB Output is correct
15 Correct 8 ms 1484 KB Output is correct
16 Correct 3 ms 952 KB Output is correct
17 Correct 4 ms 1464 KB Output is correct
18 Correct 2 ms 952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 33740 KB Output is correct
2 Correct 525 ms 34664 KB Output is correct
3 Correct 515 ms 33968 KB Output is correct
4 Correct 182 ms 30332 KB Output is correct
5 Correct 136 ms 15824 KB Output is correct
6 Correct 64 ms 16332 KB Output is correct
7 Correct 328 ms 32460 KB Output is correct
8 Correct 410 ms 34172 KB Output is correct
9 Correct 312 ms 31928 KB Output is correct
10 Correct 88 ms 14816 KB Output is correct
11 Correct 154 ms 29832 KB Output is correct
12 Correct 50 ms 17608 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 33740 KB Output is correct
2 Correct 525 ms 34664 KB Output is correct
3 Correct 515 ms 33968 KB Output is correct
4 Correct 182 ms 30332 KB Output is correct
5 Correct 136 ms 15824 KB Output is correct
6 Correct 64 ms 16332 KB Output is correct
7 Correct 328 ms 32460 KB Output is correct
8 Correct 410 ms 34172 KB Output is correct
9 Correct 312 ms 31928 KB Output is correct
10 Correct 88 ms 14816 KB Output is correct
11 Correct 154 ms 29832 KB Output is correct
12 Correct 50 ms 17608 KB Output is correct
13 Correct 576 ms 37244 KB Output is correct
14 Correct 520 ms 36528 KB Output is correct
15 Correct 553 ms 36900 KB Output is correct
16 Correct 201 ms 32016 KB Output is correct
17 Correct 165 ms 17608 KB Output is correct
18 Correct 70 ms 16872 KB Output is correct
19 Correct 568 ms 37840 KB Output is correct
20 Correct 546 ms 37992 KB Output is correct
21 Correct 539 ms 35260 KB Output is correct
22 Correct 89 ms 17100 KB Output is correct
23 Correct 141 ms 31440 KB Output is correct
24 Correct 57 ms 16304 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 9 ms 1720 KB Output is correct
8 Correct 8 ms 1716 KB Output is correct
9 Correct 8 ms 1720 KB Output is correct
10 Correct 5 ms 1460 KB Output is correct
11 Correct 4 ms 952 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 8 ms 1720 KB Output is correct
14 Correct 8 ms 1720 KB Output is correct
15 Correct 8 ms 1484 KB Output is correct
16 Correct 3 ms 952 KB Output is correct
17 Correct 4 ms 1464 KB Output is correct
18 Correct 2 ms 952 KB Output is correct
19 Correct 513 ms 33740 KB Output is correct
20 Correct 525 ms 34664 KB Output is correct
21 Correct 515 ms 33968 KB Output is correct
22 Correct 182 ms 30332 KB Output is correct
23 Correct 136 ms 15824 KB Output is correct
24 Correct 64 ms 16332 KB Output is correct
25 Correct 328 ms 32460 KB Output is correct
26 Correct 410 ms 34172 KB Output is correct
27 Correct 312 ms 31928 KB Output is correct
28 Correct 88 ms 14816 KB Output is correct
29 Correct 154 ms 29832 KB Output is correct
30 Correct 50 ms 17608 KB Output is correct
31 Correct 576 ms 37244 KB Output is correct
32 Correct 520 ms 36528 KB Output is correct
33 Correct 553 ms 36900 KB Output is correct
34 Correct 201 ms 32016 KB Output is correct
35 Correct 165 ms 17608 KB Output is correct
36 Correct 70 ms 16872 KB Output is correct
37 Correct 568 ms 37840 KB Output is correct
38 Correct 546 ms 37992 KB Output is correct
39 Correct 539 ms 35260 KB Output is correct
40 Correct 89 ms 17100 KB Output is correct
41 Correct 141 ms 31440 KB Output is correct
42 Correct 57 ms 16304 KB Output is correct
43 Correct 645 ms 48920 KB Output is correct
44 Correct 609 ms 48084 KB Output is correct
45 Correct 600 ms 49140 KB Output is correct
46 Correct 276 ms 42380 KB Output is correct
47 Correct 157 ms 20472 KB Output is correct
48 Correct 73 ms 15332 KB Output is correct
49 Correct 482 ms 45704 KB Output is correct
50 Correct 544 ms 48600 KB Output is correct
51 Correct 409 ms 44412 KB Output is correct
52 Correct 109 ms 19724 KB Output is correct
53 Correct 185 ms 39736 KB Output is correct