比赛 NOIP模拟赛1 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 天天爱射击 最终得分 100
用户昵称 Chenyao2333 运行时间 8.682 s
代码语言 C++ 内存使用 114.81 MiB
提交时间 2018-02-08 19:48:03
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

const int kN = 2e5 + 10;
const int kM = 2e5 + 10;


int N, M;
int ans[kM];
int L[kN], R[kN], S[kN];


struct Node {
    int l, r, ls, rs;
    int v;
}t[kN * 30];
int tcnt = 0;
int root[kN];

vector<int> ts[kN];

void build(int& x, int l, int r) {
    x = ++tcnt;
    t[x].l = l;
    t[x].r = r;

    if (l == r) return;
    int mid = (l+r)/2;
    build(t[x].ls, l, mid);
    build(t[x].rs, mid+1, r);
}

void insert(int& x, int p) {
    int ox = x;
    x = ++tcnt;
    t[x] = t[ox];
    t[x].v++;

    if (t[x].l == t[x].r) return;
    int mid = (t[x].l + t[x].r) / 2;
    if (p <= mid) insert(t[x].ls, p);
    else insert(t[x].rs, p);
}

int query(int x, int dx, int s) {
    if (t[x].l == t[x].r) {
        if (t[x].v - t[dx].v >= s) return t[x].l;
        else return 0;
    }

    int lsv = t[t[x].ls].v - t[t[dx].ls].v;
    if (lsv >= s) return query(t[x].ls, t[dx].ls, s);
    else return query(t[x].rs, t[dx].rs, s - lsv);
}

int main() {
    freopen("shooting.in", "r", stdin);
    freopen("shooting.out", "w", stdout);
    scanf("%d %d", &N, &M);
    int mxx = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%d %d %d", L+i, R+i, S+i);
        mxx = max(mxx, R[i]);
    }

    for (int i = 1; i <= M; i++) {
        int x;
        scanf("%d", &x);
        ts[x].push_back(i);
    }

    build(root[0], 1, N);
    for (int i = 1; i <= mxx; i++) {
        root[i] = root[i-1];
        for (int j = 0; j < ts[i].size(); j++) {
            insert(root[i], ts[i][j]);
        }
    }

    for (int i = 1; i <= N; i++) {
        //printf("x = %d, dx = %d\n", R[i], L[i]-1);
        int b = query(root[R[i]], root[L[i]-1], S[i]);
        ans[b]++;
    }

    for (int i = 1; i <= M; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}