Submission #631563

#	Time	Username	Problem	Language	Result	Execution time	Memory
631563		K4YAN	Examination (JOI19_examination)	C++17	100 / 100	1797 ms	154108 KiB

examination

//Be Name Khoda

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define po pair<pll, pll>
#define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>

const ll mxn = 1e5 + 16, MX = 27e4 + 16;
ll n, T, q, w, ans;
ll s[mxn], t[mxn], lbl[mxn], A[mxn], B[mxn], X[mxn], answer[mxn];
vector<pll> ord, qr, srt;
ordered_set v[MX];

void input() {

    cin >> n >> T;
    for(int i = 0; i < n; i++) {
        cin >> s[i] >> t[i];
        srt.push_back({s[i], i});
        ord.push_back({t[i], i});
    }
    for(int i = 0; i < T; i++) {
        ll a, b, x;
        cin >> a >> b >> x;
        qr.push_back({b, i});
        A[i] = a, B[i] = b, X[i] = x;
    }

}

int bs(int l, int r, int g) {
    if(r - l == 1) return r;
    int mid = (l + r) >> 1;
    if(srt[mid].first < g) {
        return bs(mid, r, g);
    } return bs(l, mid, g);
}

struct segtree {

    int sz = 1;
    inline void init(ll n) {
        while(sz < n) sz <<= 1;
        return;
    }
    void add(int i, pll p, int x, int lx, int rx) {
        v[x].insert(p);
        if(rx - lx == 1) return;
        int mid = (lx + rx) >> 1;
        if(i < mid) {
            add(i, p, 2 * x + 1, lx, mid);
        } else {
            add(i, p, 2 * x + 2, mid, rx);
        } return;
    }
    void add(int i, pll p) {
        add(i, p, 0, 0, sz);
        return;
    }
    void remove(int i, pll p, int x, int lx, int rx) {
        v[x].erase(p);
        if(rx - lx == 1) return;
        int mid = (lx + rx) >> 1;
        if(i < mid) {
            remove(i, p, 2 * x + 1, lx, mid);
        } else {
            remove(i, p, 2 * x + 2, mid, rx);
        } return;
    }
    void remove(int i, pll p) {
        remove(i, p, 0, 0, sz);
        return;
    }
    void ask(int l, int r, pll p, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            ans += int(v[x].size());
            ans -= v[x].order_of_key(p);
            return;
        } int mid = (lx + rx) >> 1;
        ask(l, r, p, 2 * x + 1, lx, mid);
        ask(l, r, p, 2 * x + 2, mid, rx);
        return;
    }
    void ask(int l, int r, pll p) {
        ask(l, r, p, 0, 0, sz);
        return;
    }

};

void solve() {

    sort(all(srt)), sort(all(qr));
    sort(all(ord));
    for(int i = 0; i < n; i++) {
        lbl[srt[i].second] = i;
    } ll ptr = 0;
    segtree st;
    st.init(n);
    for(int i = 0; i < n; i++) {
        st.add(i, {s[srt[i].second] + t[srt[i].second], srt[i].second});
    }
    for(int i = 0; i < T; i++) {
        while(ptr < n && ord[ptr].first < qr[i].first) {
            st.remove(lbl[ord[ptr].second], {s[ord[ptr].second] + t[ord[ptr].second], ord[ptr].second});
            ptr++;
        } ans = 0;
        q = bs(-1, n, A[qr[i].second]);
        st.ask(q, n, {X[qr[i].second], -1});
        answer[qr[i].second] = ans;
    } for(int i = 0; i < T; i++) {
        cout << answer[i] << "\n";
    } return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

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