Submission #1027392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027392		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	1670 ms	177684 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
tree_order_statistics_node_update> Tree;

const int N = 100100;
const int M = (1 << 18);

Tree st[2 * M];

void insert(int x, pair<int, int> a) {
    // cout << "added: " << '(' << x << ' ' << a.first << ')' << '\n';
    for (x += M; x; x >>= 1) {
        st[x].insert(a);
    }
}

int get(int x, int y) {
    int ans = 0;
    for (int ql = x + M, qr = 2 * M; ql < qr; ql >>= 1, qr >>= 1) {
        if (ql & 1) {
            ans += (int)st[ql].size() - st[ql].order_of_key({y, 0});
            ql++;
        } 
        if (qr & 1) {
            --qr;
            ans += (int)st[qr].size() - st[qr].order_of_key({y, 0});
        }
    }
    return ans;
}

int n, q;
pair<int, int> p[N];
array<int, 4> t[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> q;
    int res[q];

    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
    }
    for (int i = 0; i < q; i++) {
        cin >> t[i][0] >> t[i][1] >> t[i][2];
        t[i][3] = i;
    }

    vector<int> keys;
    for (int i = 0; i < n; i++) keys.push_back(p[i].first);
    for (int i = 0; i < q; i++) keys.push_back(t[i][0]);
    
    sort(keys.begin(), keys.end());
    keys.erase(unique(keys.begin(), keys.end()), keys.end());

    sort(p, p + n, [](pair<int, int> a, pair<int, int> b) {
        return a.first + a.second > b.first + b.second;
    });
    sort(t, t + q, [](array<int, 4> a, array<int, 4> b) {
        return a[2] > b[2];
    });
    
    int l = 0;
    for (int i = 0; i < q; i++) {
        auto cur = t[i];
        int z = cur[2];
        while (l < n && p[l].first + p[l].second >= z) {
            int x = lower_bound(keys.begin(), keys.end(), p[l].first) - keys.begin();
            insert(x, {p[l].second, l});
            l++;
        }
        int x = cur[0], y = cur[1];
        x = lower_bound(keys.begin(), keys.end(), x) - keys.begin();
        // cout << "ask: " << '(' << x << ' ' << y << ')' << '\n';    
        res[cur[3]] = get(x, y);
    }
    
    for (int i = 0; i < q; i++) {
        cout << res[i] << '\n';
    }

}

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