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