Submission #994191

#	Time	Username	Problem	Language	Result	Execution time	Memory
994191		Sharky	Examination (JOI19_examination)	C++17	43 / 100	246 ms	39168 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 100001;
const int INF = 1e9;

int n, q, cntq = 0, ans[N], fen[N];
vector<array<int, 3>> v;

struct Crit {
    int a, b, c, id;
    bool operator < (const Crit& o) const {
        return c > o.c;
    }
} crit[N];

struct Query {
    int ty, x, y, f, id, ti;
} qry[N << 2], tq[N << 2];

void upd(int idx, int k) {
    for (; idx <= N; idx += (idx & -idx)) fen[idx] += k;
}

int query(int idx) {
    int res = 0;
    for (; idx; idx -= (idx & -idx)) res += fen[idx];
    return res;
}

void dnc(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    for (int i = l; i <= r; i++) {
        if (qry[i].ty == 1 && qry[i].ti <= mid) upd(qry[i].y, qry[i].f);
        else if (qry[i].ty == 2 && qry[i].ti > mid) ans[qry[i].id] += qry[i].f * query(qry[i].y);
    }
    int p1 = l - 1, p2 = mid;
    for (int i = l; i <= r; i++) {
        if (qry[i].ty == 1 && qry[i].ti <= mid) upd(qry[i].y, -qry[i].f);
        if (qry[i].ti <= mid) tq[++p1] = qry[i];
        else tq[++p2] = qry[i]; 
    }
    for (int i = l; i <= r; i++) qry[i] = tq[i];
    dnc(l, mid);
    dnc(mid + 1, r);
}

void Add(int ty, int x, int y, int f, int ask, int cnt) {
    qry[cnt] = (Query) {ty, x, y, f, ask, cnt};
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1, v1, v2; i <= n; i++) {
        cin >> v1 >> v2;
        v.push_back({INF - v1, INF - v2, v1 + v2});
    }
    sort(v.begin(), v.end(), [] (array<int, 3> lhs, array<int, 3> rhs) { return lhs[2] > rhs[2]; });
    for (int i = 1; i <= q; i++) {
        cin >> crit[i].a >> crit[i].b >> crit[i].c;
        crit[i].id = i;
        crit[i].a = INF - crit[i].a, crit[i].b = INF - crit[i].b;
    }
    int ptr = 0;
    sort(crit + 1, crit + q + 1);
    vector<int> dx, dy;
    for (int i = 1; i <= q; i++) {
        while (ptr < n && v[ptr][2] >= crit[i].c) {
            Add(1, v[ptr][0], v[ptr][1], 1, 0, ++cntq);
            dx.push_back(v[ptr][0] + 1);
            dy.push_back(v[ptr][1] + 1);
            ptr++;
        }
        Add(2, crit[i].a, crit[i].b, 1, crit[i].id, ++cntq);
        dx.push_back(crit[i].a);
        dy.push_back(crit[i].b);
    }
    sort(dx.begin(), dx.end());
    dx.erase(unique(dx.begin(), dx.end()), dx.end());
    sort(dy.begin(), dy.end());
    dy.erase(unique(dy.begin(), dy.end()), dy.end());
    for (int i = 1; i <= cntq; i++) {
        qry[i].x = lower_bound(dx.begin(), dx.end(), qry[i].x) - dx.begin() + 1;
        qry[i].y = lower_bound(dy.begin(), dy.end(), qry[i].y) - dy.begin() + 1;
    }
    sort(qry + 1, qry + cntq + 1, [] (Query lhs, Query rhs) { return tie(lhs.x, lhs.y, lhs.ty) < tie(rhs.x, rhs.y, rhs.ty); });
    dnc(1, cntq);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

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