제출 #1348965

#제출 시각아이디문제언어결과실행 시간메모리
1348965anteknneExamination (JOI19_examination)C++20
100 / 100
1418 ms241316 KiB
#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 long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 200 * 1000 + 17;
ordered_set st[4 * MAXN];
vector<int> v1;
map<int, vector<pair<pii, int>>> zap;
map<int, vector<pii>> dod;
set<int> czasy;
int wyn[MAXN];
int cnt = 0;

void aktualizuj (int p, int k, int ind, int w, int i) {
    if (p > ind || k < ind) {
        return;
    }
    st[i].insert({w, cnt});
    cnt ++;
    if (p == k) {
        return;
    }
    int sr = (p + k)/ 2;
    aktualizuj(p, sr, ind, w, i * 2);
    aktualizuj(sr + 1, k, ind, w, i * 2 + 1);
}

int zapytanie (int p, int k, int a, int b, int x, int i) {
    if (p > b || k < a) {
        return 0;
    }
    if (a <= p && k <= b) {
        return int(st[i].size()) - st[i].order_of_key({x, 0});
    }
    int sr = (p + k)/ 2;
    return (zapytanie(p, sr, a, b, x, i * 2) + zapytanie(sr + 1, k, a, b, x, i * 2 + 1));
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    int s, t;
    for (int i = 0; i < n; i ++) {
        cin >> s >> t;
        czasy.insert(-(s + t));
        dod[-(s + t)].pb({s, t});
        v1.pb(s);
    }

    int a, b, c;
    for (int i = 0; i < q; i ++) {
        cin >> a >> b >> c;
        czasy.insert(-c);
        zap[-c].pb({{a, b}, i});
        v1.pb(a);
    }

    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());

    int n1 = int(v1.size());

    for (auto x : czasy) {
        for (auto y : dod[x]) {
            aktualizuj(0, n1 - 1, lower_bound(v1.begin(), v1.end(), y.st) - v1.begin(), y.nd, 1);
        }
        for (auto y : zap[x]) {
            wyn[y.nd] = zapytanie(0, n1 - 1, lower_bound(v1.begin(), v1.end(), y.st.st) - v1.begin(), n1 - 1, y.st.nd, 1);
        }
    }

    for (int i = 0; i < q; i ++) {
        cout << wyn[i] << "\n";
    }

    return 0;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...