oj.uz

Submission #709242

# Submission time Handle Problem Language Result Execution time Memory
709242 2023-03-13T09:20:34 Z finn__ Examination (JOI19_examination) C++17
0 / 100
 658 ms 35856 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 15 ms 1584 KB Output is correct
8 Correct 13 ms 1576 KB Output is correct
9 Correct 10 ms 1584 KB Output is correct
10 Correct 7 ms 1444 KB Output is correct
11 Correct 5 ms 852 KB Output is correct
12 Incorrect 3 ms 840 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 35808 KB Output is correct
2 Correct 557 ms 35856 KB Output is correct
3 Correct 554 ms 35768 KB Output is correct
4 Correct 225 ms 30204 KB Output is correct
5 Correct 202 ms 16624 KB Output is correct
6 Incorrect 87 ms 15216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 35808 KB Output is correct
2 Correct 557 ms 35856 KB Output is correct
3 Correct 554 ms 35768 KB Output is correct
4 Correct 225 ms 30204 KB Output is correct
5 Correct 202 ms 16624 KB Output is correct
6 Incorrect 87 ms 15216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 15 ms 1584 KB Output is correct
8 Correct 13 ms 1576 KB Output is correct
9 Correct 10 ms 1584 KB Output is correct
10 Correct 7 ms 1444 KB Output is correct
11 Correct 5 ms 852 KB Output is correct
12 Incorrect 3 ms 840 KB Output isn't correct
13 Halted 0 ms 0 KB -