Submission #907742

#	Time	Username	Problem	Language	Result	Execution time	Memory
907742		trMatherz	Examination (JOI19_examination)	C++17	100 / 100	645 ms	49140 KiB

examination

#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 (stderr)

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57