Submission #702416

#	Time	Username	Problem	Language	Result	Execution time	Memory
702416		PixelCat	Examination (JOI19_examination)	C++14	20 / 100	3080 ms	65548 KiB

examination

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;

#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
struct SegTree {
    vector<int> st[MAXN << 2], t[MAXN << 2];
    void build(int id, int l, int r, vector<int> &vs, vector<vector<int>> &vt) {
        For(it, l, r) for(auto &j:vt[it]) {
            t[id].eb(j);
            st[id].eb(vs[it] + j);
        }
        sort(all(t[id]));
        sort(all(st[id]));
        if(l == r) return;
        int m = (l + r) / 2;
        build(L(id), l, m, vs, vt);
        build(R(id), m + 1, r, vs, vt);
    }
    int count(const vector<int> &v, int x) {
        return v.end() - lower_bound(all(v), x);
    }
    int ask(int id, int l, int r, int L, int R, int type, int x) {
        if(l >= L && r <= R) {
            if(type) return count(t[id], x);
            return count(st[id], x);
        }
        int m = (l + r) / 2;
        if(R <= m) return ask(L(id), l, m, L, R, type, x);
        if(L > m)  return ask(R(id), m + 1, r, L, R, type, x);
        return ask(L(id), l, m, L, R, type, x) +
               ask(R(id), m + 1, r, L, R, type, x);
    }
} seg;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nyanyanyanyanya
    int n, q; cin >> n >> q;
    vector<pii> pts;
    vector<int> vs;
    For(i, 1, n) {
        int s, t; cin >> s >> t;
        pts.eb(s, t);
        vs.eb(s);
    }
    sort(all(vs));
    vs.erase(unique(all(vs)), vs.end());
    int m = sz(vs);
    vector<vector<int>> vt(m);
    for(auto &p:pts) {
        int it = lower_bound(all(vs), p.F) - vs.begin();
        vt[it].eb(p.S);
    }
    seg.build(0, 0, m - 1, vs, vt);
    while(q--) {
        int a, b, c; cin >> a >> b >> c;
        int res;
        if(a + b >= c) {
            int p = lower_bound(all(vs), a) - vs.begin();
            res = seg.ask(0, 0, m - 1, p, m, 1, b);
        } else {
            int p1 = lower_bound(all(vs), a) - vs.begin();
            int p2 = lower_bound(all(vs), c - b) - vs.begin();
            res = seg.ask(0, 0, m - 1, p1, p2 - 1, 0, c) +
                  seg.ask(0, 0, m - 1, p2, m, 1, b);
        }
        cout << res << "\n";
    }
    return 0;
}

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