比赛 |
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;
}