제출 #1167139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167139		ali2241	Examination (JOI19_examination)	C++20	100 / 100	1644 ms	196416 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 arr2 array<int, 2>
#define arr3 array<int, 3>
#define all(a) a.begin(), a.end()
#define double long double
#define ctz __builtin_ctz
#define clz __builtin_clz
#define popcount __builtin_popcount
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")

using namespace std;
using namespace __gnu_pbds;

//I got tired from div.2s



// template<class T> using rb3 = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using mrb3 = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// bool comp(arr2 a, arr2 b) {
//     return (a[0] - a[1]) < (b[0] - b[1]);
// }

const int N = (1 << 19), M = 998244353;

vector<int> sum[N];
arr2 arr[N];
vector<int> cmp = {2000000010};

int ths = N;

int ans[N];
array<int, 4> que[N];
int n, q;

struct Mst {
    mrb3<int> seg[2 * N];
    void upd(int a, int b) {
        seg[a += N].insert(b);
        for (a >>= 1; a > 0; a >>= 1) {
            seg[a].insert(b);
        }
    }
    int get(int l, int r, int a) {
        int ans = 0;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                ans += seg[l++].order_of_key(a + 1);
            }
            if (r & 1) {
                ans += seg[--r].order_of_key(a + 1);
            }
        }
        return ans;
    }
} seg;

int ind(int a) {
    return (lower_bound(all(cmp), a) - cmp.begin());
}

void compress() {
    sort(all(cmp));
    cmp.resize(unique(all(cmp)) - cmp.begin());
    for (int i = 0; i < n; ++i) {
        sum[ind(arr[i][0] + arr[i][1])].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
        arr[i][0] = ind(arr[i][0]);
        arr[i][1] = ind(arr[i][1]);
    }
    for (int i = 0; i < q; ++i) {
        que[i][0] = ind(que[i][0]);
        que[i][1] = ind(que[i][1]);
        que[i][2] = ind(que[i][2]);
    }
}

void fun() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i][0] >> arr[i][1];
        cmp.push_back(arr[i][0]);
        cmp.push_back(arr[i][1]);
        cmp.push_back(arr[i][0] + arr[i][1]);
    }
    for (int i = 0; i < q; ++i) {
        cin >> que[i][1] >> que[i][2] >> que[i][0];
        que[i][3] = i;
    }
    sort(que, que + q, greater<array<int, 4>>());
    compress();
    for (int i = 0; i < q; ++i) {
        while (que[i][0] < ths) {
            ths--;
            for (int j : sum[ths]) {
                seg.upd(arr[j][0], -arr[j][1]);
                // cout << cmp[arr[j][1]] << " ";
            }
        }
        // cout << ";\n" << cmp[ths] << "\n";
        ans[que[i][3]] = seg.get(que[i][1], N, -que[i][2]);
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

int32_t main() {
    // pre();
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // int tc;
    // cin >> tc;
    // while (tc--)
    fun();
}

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