Submission #1074869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074869		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	428 ms	31188 KiB

examination

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define lb(s, a) lower_bound(all(s), (a)) - s.begin()

using namespace std;

typedef long long ll;

const int ar = 2e5 + 2;
const ll mod = 1e9 + 7;
const int oo = 2e9;

struct BIT {
    vector<vector<int>> c, t;
    bool b;

    BIT(int n) {
        b = 0;
        c = vector<vector<int>>(n);
        t = vector<vector<int>>(n);
    }

    void init() {
        b = 1;
        for (int 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<int>(c[i].size(), 0);
        }
    }

    void update(int i, int j) {
        i++, j++;
        while (i <= t.size()) {
            if (!b)
                c[i - 1].push_back(j);
            else {
                int 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;
        }
    }

    int pre(int i, int j) {
        int x = 0;
        i++, j++;

        while (i) {
            int 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;
    }

    int get(int i1, int i2, int j1, int j2) {
        int x = pre(i2, j2);
        if (i1)
            x -= pre(i1 - 1, j2);
        if (j1)
            x -= pre(i2, j1 - 1);
        if (i1 && j1)
            x += pre(i1 - 1, j1 - 1);
        return x;
    }
};

struct Event {
    int t, x, y;
    int i;
    bool a;

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

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#define task "code"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int n, q;
    cin >> n >> q;

    vector<Event> tap;
    vector<int> td;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        td.push_back(x);
        tap.push_back({x + y, x, y, n, 1});
    }

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        td.push_back(x);
        tap.push_back({z, x, y, i, 0});
    }

    sort(all(tap));
    sort(all(td));
    td.resize(unique(all(td)) - td.begin());
    BIT bit(td.size());

    vector<int> ans(q, 0);

    for (auto const &[t, x, y, i, a] : tap)
        if (a)
            bit.update(lb(td, x), y);
    bit.init();
    for (auto const &[t, x, y, i, a] : tap) {
        if (a)
            bit.update(lb(td, x), y);
        else
            ans[i] = bit.get(lb(td, x), td.size() - 1, y, oo);
    }

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

Compilation message (stderr)

examination.cpp: In member function 'void BIT::init()':
examination.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i = 0; i < c.size(); i++) {
      |                         ~~^~~~~~~~~~
examination.cpp: In member function 'void BIT::update(int, int)':
examination.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while (i <= t.size()) {
      |                ~~^~~~~~~~~~~
examination.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 while (k <= c[i - 1].size()) {
      |                        ~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57