MLE求助
查看原帖
MLE求助
149192
__gcd楼主2021/1/27 20:46

rt,样例就MLE了,不知道为什么

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
inline int read() {
	int x = 0; bool op = 0;
	char c = getchar();
	while(!isdigit(c))op |= (c == '-'), c = getchar();
	while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return op ? -x : x;
}
const int N = 250010;
int n, siz, ans, tot;
int x[N], y[N], p[N], r[N], m[N], lsh[N * 2], que[N], tag[N << 2];
bool del[N];
db dis[N];
queue<int> tree[N << 2], u;
void disc() {
	sort(lsh + 1, lsh + 1 + tot);
	siz = unique(lsh + 1, lsh + 1 + tot) - (lsh + 1);
	for(int i = 1; i <= n; i++) {
		if(i ^ 1)m[i] = lower_bound(lsh + 1, lsh + 1 + siz, m[i]) - lsh;
		p[i] = lower_bound(lsh + 1, lsh + 1 + siz, p[i]) - lsh;
	}
	return ;
}
db dist(int i, int j) {return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));}
bool cmp(int x, int y) {return dis[x] < dis[y];}
void update(int k, int l, int r, int pos, int val) {
	tree[k].push(val);
	if(l == r)return ;
	int mid = l + r >> 1;
	if(pos <= mid)update(k * 2, l, mid, pos, val);
	else update(k * 2 + 1, mid + 1, r, pos, val);
	return ;
}
void query(int k, int l, int r, int qx, int qy, int val) {
	if(l >= qx && r <= qy) {
		while(tree[k].empty() == false && dis[tree[k].front()] <= val) {
			if(del[tree[k].front()] == false) {ans++; u.push(tree[k].front()); del[tree[k].front()] = true;}
			tree[k].pop(); 
		}
		tag[k] = max(tag[k], val);
		return ;
	}
	tag[k * 2] = max(tag[k * 2], tag[k]); tag[k * 2 + 1] = max(tag[k * 2 + 1], tag[k]);
	int mid = l + r >> 1;
	if(qx <= mid)query(k * 2, l, mid, qx, qy, val);
	if(qy > mid)query(k * 2 + 1, mid + 1, r, qx, qy, val);
	return ;
}
int main() {
	x[1] = read(); y[1] = read(); p[1] = read(); r[1] = read();
	lsh[++tot] = p[1];
	n = read(); n++;
	for(int i = 2; i <= n; i++) {
		x[i] = read(); y[i] = read(); m[i] = read(); p[i] = read(); r[i] = read();
		lsh[++tot] = m[i]; lsh[++tot] = p[i]; dis[i] = dist(i, 1); que[i - 1] = i;
	}
	disc(); sort(que + 1, que + n, cmp);
	for(int i = 1; i < n; i++) {
		update(1, 1, siz, m[que[i]], que[i]);
	}
	u.push(1);
	while(u.empty() == false) {
		int cur = u.front(); u.pop();
		query(1, 1, siz, 1, p[cur], r[cur]);
	}
	printf("%d", ans);
	return 0;
}
2021/1/27 20:46
加载中...