帮帮孩子卡常吧
  • 板块CF19D Points
  • 楼主Link_Cut_Y
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/7 21:21
  • 上次更新2024/1/8 13:58:01
查看原帖
帮帮孩子卡常吧
519384
Link_Cut_Y楼主2024/1/7 21:21

真的球球了!!卡了两个小时了

一直卡不过 #13,写的两个 log⁡\log 的树状数组套 set。

悬关两个。

#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rep(i, a, b) for (register int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (register int i = (a); i < (b); i ++ )
 
using namespace std;
 
#define gc getchar
#define pc putchar
 
inline int read() {
	int s = 0, f = 0; char ch = gc();
	while (ch < '0' or ch > '9') { if (ch == '-') f = 1; ch = gc(); }
	while (ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + (ch ^ 48); ch = gc(); }
	return f ? -s : s;
}
inline void print(int x){
    if(x <= 9) putchar('0' + x);
    else print(x / 10), putchar('0' + x % 10);
}
typedef pair<int, int> PII;
const int N = 200010;
const int INF = 0x3f3f3f3f;
set<PII> s[N];
int n, lim, p[N];
struct Q {
	int op, x, y;
}q[N];
inline int find(int x) {
	return lower_bound(p + 1, p + lim, x) - p;
}
inline void add(int k, int x, int y) {
	for (int i = k; i; i -= (i & -i))
		s[i].insert(mp(x, y));
}
inline void del(int k, int x, int y) {
	for (int i = k; i; i -= (i & -i))
		s[i].erase(mp(x, y));
}
inline PII ask(int k, int x, int y) {
	PII ans = mp(INF, INF);
	for (int i = k; i <= lim; i += (i & -i))
		ans = min(ans, *s[i].lower_bound(mp(x, y)));
	return ans;
}
int main() {
	n = read();
	rep(i, 1, n) {
		char ch[7]; int x, y;
		scanf("%s", ch); x = read(), y = read();
		if (*ch == 'a') q[i] = {0, x, y};
		if (*ch == 'r') q[i] = {1, x, y};
		if (*ch == 'f') q[i] = {2, ++ x, ++ y};
		p[ ++ lim] = y;
	} sort(p + 1, p + lim + 1);
	lim = unique(p + 1, p + lim + 1) - p + 1;
	rep(i, 1, lim) s[i].insert(mp(INF, INF));
	rep(i, 1, n) {
		if (q[i].op == 0) add(find(q[i].y), q[i].x, q[i].y);
		if (q[i].op == 1) del(find(q[i].y), q[i].x, q[i].y);
		if (q[i].op == 2) {
			register PII ans = ask(find(q[i].y), q[i].x, q[i].y);
			if (ans.first == INF) pc('-'), pc('1'), pc('\n');
			else print(ans.first), pc(' '), print(ans.second), pc('\n');
		}
	} return 0;
}
2024/1/7 21:21
加载中...