Submission #1225094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225094		Double_Slash	Examination (JOI19_examination)	C++20	100 / 100	269 ms	5084 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> cc;
    pint p[n];
    for (auto &[x, y]: p) {
        cin >> x >> y;
        cc.emplace_back(y);
    }
    sort(all(cc));
    cc.erase(unique(all(cc)), cc.end());
    auto lb = [&] (int x) { return lower_bound(all(cc), x) - cc.begin(); };
    array<int, 4> queries[q];
    for (int i = q; i--;) {
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
        queries[i][3] = i;
    }
    int ans[q]{};
    sort(p, p + n);
    sort(queries, queries + q);
    struct St {
        int n;
        vector<int> st;

        St(int n) : n(n), st(n << 1) {}

        void upd(int i) {
            for (i += n; i; i >>= 1) ++st[i];
        }

        int query(int l, int r) {
            int ret = 0;
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if (l & 1) ret += st[l++];
                if (r & 1) ret += st[--r];
            }
            return ret;
        }
    } st{cc.size()};
    for (int i = q, j = n; i--;) {
        auto [a, b, c, idx] = queries[i];
        while (j and p[j - 1].first >= a) st.upd(lb(p[--j].second));
        ans[idx] = st.query(lb(max(b, c - a)), cc.size());
    }
    sort(p, p + n, [] (auto &a, auto &b) { return a.first + a.second < b.first + b.second; });
    sort(queries, queries + q, [] (auto &a, auto &b) { return a[2] < b[2]; });
    fill(all(st.st), 0);
    for (int i = q, j = n; i--;) {
        auto [a, b, c, idx] = queries[i];
        while (j and p[j - 1].first + p[j - 1].second >= c) st.upd(lb(p[--j].second));
        ans[idx] += st.query(lb(b), lb(c - a));
    }
    for (int i = q; i--;) cout << ans[i] << endl;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:45:17: warning: narrowing conversion of 'cc.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   45 |     } st{cc.size()};
      |          ~~~~~~~^~

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