Submission #1110753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110753		anmattroi	Examination (JOI19_examination)	C++14	100 / 100	417 ms	57180 KiB

examination

#include <bits/stdc++.h>

#define maxn 100005
#define fi first
#define se second

using namespace std;
using ii = pair<int, int>;

int n, q;

int itone[22*maxn], ittwo[22*maxn], Lone[22*maxn], Ltwo[22*maxn], Rone[22*maxn], Rtwo[22*maxn];
int rootone[maxn], roottwo[maxn], ntone = 0, nttwo = 0;

int buildone(int lo = 1, int hi = n) {
    if (lo == hi) return ++ntone;
    int cur = ++ntone, mid = (lo + hi) >> 1;
    Lone[cur] = buildone(lo, mid);
    Rone[cur] = buildone(mid+1, hi);
    return cur;
}

int buildtwo(int lo = 1, int hi = n) {
    if (lo == hi) return ++nttwo;
    int cur = ++nttwo, mid = (lo + hi) >> 1;
    Ltwo[cur] = buildtwo(lo, mid);
    Rtwo[cur] = buildtwo(mid+1, hi);
    return cur;
}

int updone(int u, int oldver, int lo = 1, int hi = n) {
    if (lo == hi) {
        itone[++ntone] = itone[oldver] + 1;
        return ntone;
    }
    int cur = ++ntone, mid = (lo + hi) >> 1;
    if (u <= mid) {
        Lone[cur] = updone(u, Lone[oldver], lo, mid);
        Rone[cur] = Rone[oldver];
    } else {
        Lone[cur] = Lone[oldver];
        Rone[cur] = updone(u, Rone[oldver], mid+1, hi);
    }
    itone[cur] = itone[Lone[cur]] + itone[Rone[cur]];
    return cur;
}

int updtwo(int u, int oldver, int lo = 1, int hi = n) {
    if (lo == hi) {
        ittwo[++nttwo] = ittwo[oldver] + 1;
        return nttwo;
    }
    int cur = ++nttwo, mid = (lo + hi) >> 1;
    if (u <= mid) {
        Ltwo[cur] = updtwo(u, Ltwo[oldver], lo, mid);
        Rtwo[cur] = Rtwo[oldver];
    } else {
        Ltwo[cur] = Ltwo[oldver];
        Rtwo[cur] = updtwo(u, Rtwo[oldver], mid+1, hi);
    }
    ittwo[cur] = ittwo[Ltwo[cur]] + ittwo[Rtwo[cur]];
    return cur;
}

int getone(int u, int v, int r, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return itone[r];
    int mid = (lo + hi) >> 1;
    return getone(u, v, Lone[r], lo, mid) + getone(u, v, Rone[r], mid+1, hi);
}

int gettwo(int u, int v, int r, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return ittwo[r];
    int mid = (lo + hi) >> 1;
    return gettwo(u, v, Ltwo[r], lo, mid) + gettwo(u, v, Rtwo[r], mid+1, hi);
}

ii a[maxn];

int b[maxn], c[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se;
        b[i] = a[i].se;
        c[i] = a[i].fi + a[i].se;
    }
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);

    sort(a + 1, a + n + 1);

    rootone[0] = buildone();
    roottwo[0] = buildtwo();

    for (int i = 1; i <= n; i++) {
        int p1 = lower_bound(b + 1, b + n + 1, a[i].se) - b,
            p2 = lower_bound(c + 1, c + n + 1, a[i].fi+a[i].se) - c;
        rootone[i] = updone(p1, rootone[i-1]);
        roottwo[i] = updtwo(p2, roottwo[i-1]);
    }

    auto solve = [&]() -> void {
        int x, y, z;
        cin >> x >> y >> z;
        int L1 = lower_bound(a + 1, a + n + 1, ii{x, 0}) - a;

        if (L1 > n) {
            cout << "0\n";
            return;
        }

        int lo = L1-1, hi = n+1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (a[mid].fi + y >= z) hi = mid;
            else lo = mid;
        }
        int p1 = lower_bound(b + 1, b + n + 1, y) - b, p2 = lower_bound(c + 1, c + n + 1, z) - c;

        int ans = 0;
        if (p2 <= n) ans += gettwo(p2, n, roottwo[lo]) - gettwo(p2, n, roottwo[L1-1]);
        if (p1 <= n) ans += getone(p1, n, rootone[n]) - getone(p1, n, rootone[lo]);

        cout << ans << "\n";
    };

    while (q--) solve();
}
/*
5 4
20 95
35 100
45 15
70 70
80 40
20 50 120
10 10 100
60 60 80
0 100 100
*/

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