比赛 |
4043级2023省选练习赛3 |
评测结果 |
AAWAWWAAWAAAAAWAAAAA |
题目名称 |
考试 |
最终得分 |
75 |
用户昵称 |
zxhhh |
运行时间 |
3.650 s |
代码语言 |
C++ |
内存使用 |
38.27 MiB |
提交时间 |
2023-03-08 20:50:44 |
显示代码纯文本
#include <bits/stdc++.h>
#define lowbit(a) ((a) & (-a))
using namespace std;
const int N = 1e5 + 5;
inline int read () {
int num = 0; char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
return num;
}
int n, q, a[N][3], t[N << 3], idx, qs[N][3], ans[N];
typedef long long ll;
ll c[N<<3];
void add (int idx, int x) {
while (idx <= (n << 3)) c[idx] += x, idx += lowbit(idx);
}
ll query (int idx) {
ll res = 0; while (idx) res += c[idx], idx -= lowbit(idx); return res;
}
int addt[N << 3];
struct node {
int a, b, c, idx;
}nodes[N<<3], tmp[N<<3];
bool cmp (node a, node b) {
if (a.a != b.a) return a.a < b.a;
if (a.b != b.b) return a.b < b.b;
return a.c < b.c;
}
void cdq (int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1, adl = 0;
cdq(l, mid); cdq(mid + 1, r);
int tl = l, tr = mid + 1;
for (int i = l;i <= r;i++) {
if ((tl <= mid) && ((tr > r) || (nodes[tl].b < nodes[tr].b || (nodes[tl].b == nodes[tr].b && nodes[tl].c < nodes[tr].c)))) {
if (!nodes[tl].idx) {
add(nodes[tl].c, 1), addt[++adl] = nodes[tl].c;
}
tmp[i] = nodes[tl]; tl++;
}
else {
if (nodes[tr].idx) ans[nodes[tr].idx] += query(nodes[tr].c);
tmp[i] = nodes[tr]; tr++;
}
}
for (int i = 1;i <= adl;i++) add(addt[i], -1);
for (int i = l;i <= r;i++) nodes[i] = tmp[i];
}
int main () {
freopen("Examination.in", "r", stdin);
freopen("Examination.out", "w", stdout);
n = read(), q = read();
for (int i = 1;i <= n;i++) t[++idx] = a[i][0] = read(), t[++idx] = a[i][1] = read(), t[++idx] = a[i][2] = a[i][0] + a[i][1];
for (int i = 1;i <= q;i++) t[++idx] = qs[i][0] = read(), t[++idx] = qs[i][1] = read(), t[++idx] = qs[i][2] =read();
// for (int i = 1;i <= n;i++) cout << a[i][0] << " " <<a[i][1] << endl;
sort(t + 1, t +1 + idx);
// for (int i= 1;i <= idx;i++) cout << t[i] << " "; cout <<endl;
int tl = unique (t + 1, t + 1 + idx) - t; idx = 0;
for (int i = 1;i <= n;i++) a[i][0] = upper_bound(t + 1, t+1+tl, a[i][0]) - t - 1, a[i][1] = upper_bound(t + 1, t+1+tl, a[i][1]) - t - 1, a[i][2] = upper_bound(t + 1, t+1+tl, a[i][2]) - t - 1;
// for (int i = 1;i <= n;i++) cout << tl <<" " << a[i][0] <<" " << a[i][1] << " " << a[i][2] <<endl;
for (int i = 1;i <= q;i++) qs[i][0] = upper_bound(t + 1, t+1+tl, qs[i][0]) - t - 1, qs[i][1] = upper_bound(t + 1, t+1+tl, qs[i][1]) - t - 1, qs[i][2] = upper_bound(t + 1, t+1+tl, qs[i][2]) - t - 1;
for (int i = 1;i <= n;i++) nodes[++idx] = (node){tl-a[i][0]+1, tl-a[i][1]+1, tl-a[i][2]+1, 0};
for (int i = 1;i <= q;i++) nodes[++idx] = (node){tl-qs[i][0]+1, tl-qs[i][1]+1, tl-qs[i][2]+1, i};
sort (nodes+1, nodes+1+idx, cmp);
// for (int i = 1;i <= idx;i++) cout << nodes[i].a <<" " << nodes[i].b << " " << nodes[i].c << endl;
cdq(1, idx);
// for (int i = 1;i <= idx;i++) cout << nodes[i].a <<" " << nodes[i].b << " " << nodes[i].c << endl;
for (int i = 1;i <= q;i++) printf("%d\n", ans[i]);
return 0;
}