Submission #1015269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015269		aufan	Examination (JOI19_examination)	C++17	100 / 100	1242 ms	151912 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define fi first
#define se second
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

struct node {
        ordered_multiset ms;
        int st, en;
        node *left, *right;

        void build(int start, int end) {
                st = start;
                en = end;

                if (st == en) {
                        return;
                }

                int md = (st + en) / 2;
                left = new node();
                right = new node();

                left->build(st, md);
                right->build(md + 1, en);
        }

        int query(int lf, int rg, int x) {
                if (st > rg || en < lf) return 0ll;
                if (lf <= st && en <= rg) return (int)ms.size() - ms.order_of_key(x);
                return left->query(lf, rg, x) + right->query(lf, rg, x);
        }

        void update(int id, int x) {
                if (st > id || en < id) return;
                ms.insert(x);
                if (st == en) return;

                left->update(id, x);
                right->update(id, x);
        }
} sg;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, q;
        cin >> n >> q;

        vector<int> s(n), t(n);
        for (int i = 0; i < n; i++) cin >> s[i] >> t[i];

        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
                return s[x] + t[x] > s[y] + t[y];
        });

        vector<array<int, 4>> qr;
        for (int i = 0; i < q; i++) {
                int x, y, z;
                cin >> x >> y >> z;

                qr.push_back({x, y, z, i});
        }
        sort(qr.begin(), qr.end(), [&](auto x, auto y) {
                return x[2] > y[2];
        });

        vector<int> b;
        for (int i = 0; i < n; i++) b.push_back(s[i]);
        sort(b.begin(), b.end());
        b.erase(unique(b.begin(), b.end()), b.end());

        int m = (int)b.size();
        sg.build(1, m);

        auto get = [&](int x) {
                return lower_bound(b.begin(), b.end(), x) - b.begin();
        };

        int p = 0;
        vector<int> ans(q);
        for (auto [x, y, z, i] : qr) {
                while (p < n && s[ord[p]] + t[ord[p]] >= z) {
                        sg.update(get(s[ord[p]]) + 1, t[ord[p]]);
                        p += 1;
                }

                ans[i] = sg.query(get(x) + 1, m, y);
        }

        for (int i = 0; i < q; i++) cout << ans[i] << '\n';
        
        return 0;
}

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