QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#752830#4906. 球球NineSunsJudging//C++144.7kb2024-11-16 10:02:082024-11-16 10:02:16

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 10:02:16]
  • 评测
  • 测评结果:Judging
  • 用时:0ms
  • 内存:0kb
  • [2024-11-16 10:02:08]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
#define gc getchar
#define lowbit(x) (x&-x)

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6+5, inf = 0x3f3f3f3f3f3f3f3f; 
int n, g[N], t[N], x[N], gp[N], tx[N], c[N], ed, m;
pii stk[N*20]; 
bool h[N]; 
inline int read () {
	int x = 0, f = 1; char ch = gc(); 
	while (!isdigit(ch)) {
		if (ch == '-') f = -1; 
		ch = gc(); 
	}
	while (isdigit(ch)) x = x*10+(ch^48), ch = gc(); 
	return x*f; 
}
inline void add (int x, int k) {
	for (; x <= m; x += lowbit(x)) c[x] += k; 
}
inline int qs (int x) {
	int res = 0; 
	for (; x; x -= lowbit(x)) res += c[x];
	return res;
}

void clr () {
////	cout << "CLR\n"; 
	while (ed) {
		add(stk[ed].fi, -1); add(stk[ed].se+1, 1); 
		ed--; 
	}
//	memset(c, 0, sizeof c); 
}

bool chk (int x) {
//	cout << "FIND:" << x << " "; 
	x = lower_bound(tx+1, tx+1+m, x)-tx; 
	return qs(x); 
}

inline void ins (int l, int r) {
	if (l > r) return; 
	l = lower_bound(tx+1, tx+1+m, l)-tx; 
	r = upper_bound(tx+1, tx+1+m, r)-tx-1;
	if (l > r) return; 
//	cout << l << " " << r << endl; 
	add(l, 1); add(r+1, -1); 
	stk[++ed] = {l, r}; 
//	while (it != f.end() && (*it).se)
}

void solve () {
	n = read(); 
	for (int i = 1;i <= n;i++) t[i] = read(), x[i] = read(), tx[i] = x[i];
	sort(tx+1, tx+1+n); m = unique(tx+1, tx+1+n)-tx-1; 
	memset(g, 0x3f, sizeof g); memset(gp, -1, sizeof gp); 
	g[0] = 0; h[0] = 1; 
	for (int i = 0;i <= n;i++) {
		if (i) g[i] = min(g[i], max(t[i-1], g[i-1]+abs(x[i]-x[i-1]))); 
		if (i && x[i] == x[i-1]) g[i] = min(g[i], g[i-1]);  
		if (i < n && chk(x[i+1])) gp[i+1] = i; 
//		cout << "IDX:" << i << endl; 
		if (i && t[i+1]-t[i] < abs(x[i+1]-x[i])) {
			clr(); //cout << "CLEAR" << endl; 
		} 
//		if (t[i+1]-t[i] >= abs(x[i+1]-x[i])) for (int j = 0;j <= n;j++) f[i+1][j] |= f[i][j]; 
		
		if (i < n && h[i]) {
			h[i+1] |= (t[i+1]-t[i] >= abs(x[i+1]-x[i])); 
			g[i+1] = min(g[i+1], t[i]+abs(x[i+1]-x[i])); 
			int T = t[i+1]-t[i]; 
			
			ins(ceil(1.0*(x[i]+x[i+1]-T)/2), min(x[i], x[i+1])); 
			if (x[i] <= x[i+1] && x[i]-x[i+1] <= T) ins(x[i+1], x[i]); 
			if (x[i] > x[i+1] && x[i+1]-x[i] <= T) ins(x[i], x[i+1]); 
			ins(max(x[i], x[i+1]), floor(1.0*(T+x[i]+x[i+1])/2)); 
//			for (int j = 1;j <= n;j++) {
//				if (abs(x[j]-x[i])+abs(x[i+1]-x[j]) <= t[i+1]-t[i]) ins(x[j], x[j]); 
//			}
//			for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-t[i] >= abs(x[j]-x[i])+abs(x[i+1]-x[j]); 
		}
		if (i && i < n) {
			int j; 
			if (x[i] == x[i-1] && ~gp[i-1]) gp[i] = j = gp[i-1];  
			else j = gp[i]; 
//			cout << "CHECK:" << i << " " << j << endl; 
			if (~j && j == i-1)  {
				g[i+1] = min(g[i+1], max(t[i], t[j]+abs(x[i+1]-x[j])));
				h[i+1] |= t[i+1]-t[j] >= abs(x[i+1]-x[j]); 
				if (t[i+1]-t[j] >= abs(x[i+1]-x[j])) ins(x[i], x[i]); 
				
				ins(ceil(1.0*(x[i+1]-t[i+1]+t[j]+x[j])/2), min({x[j], x[i+1], t[j]-t[i]+x[j]})); 
				ins(max(t[j]+x[j]-t[i], x[i+1]+t[i]-t[i+1]), min(x[j], x[i+1])); 
				ins(max(x[i+1], t[j]+x[j]-t[i]), min(x[j], t[i+1]-t[i]+x[i+1])); 
				if (t[i+1]+x[i+1]-t[j]-x[j] >= 0) ins(x[i+1], min(t[j]+x[j]-t[i], x[j]));
				ins(max(x[j], x[i+1]+t[i]-t[i+1]), min(t[i]+x[j]-t[j], x[i+1]));
				if (t[i+1]-t[j]+x[j]-x[i+1] >= 0) ins(max(x[j], t[i]+x[j]-t[j]), x[i+1]); 
				ins(max(x[j], x[i+1]), min(t[i]-t[j]+x[j], t[i+1]+x[i+1]-t[i]));
				ins(max({x[j], x[i+1], t[i]-t[j]+x[j]}), floor(1.0*(t[i+1]-t[j]+x[j]+x[i+1])/2)); 
				
//				for (int z = i+1;z <= n;z++) {
//					if (t[i+1]-max(t[i], t[j]+abs(x[j]-x[z])) >= abs(x[z]-x[i+1])) ins(x[z], x[z]); 
//				}
			}
		}
		if (g[i] > t[i]) g[i] = inf; 
		if (g[i] <= t[i] && i < n) {
			h[i+1] |= t[i+1]-g[i] >= abs(x[i+1]-x[i]); 
			if (t[i+1]-g[i] >= abs(x[i+1]-x[i])) ins(x[i], x[i]);
			
			ins(ceil(1.0*(x[i+1]-t[i+1]+g[i]+x[i])/2), min({x[i], x[i+1], g[i]-t[i]+x[i]})); 
			ins(max(g[i]+x[i]-t[i], x[i+1]+t[i]-t[i+1]), min(x[i], x[i+1])); 
			ins(max(x[i+1], g[i]+x[i]-t[i]), min(x[i], t[i+1]-t[i]+x[i+1])); 
			if (t[i+1]+x[i+1]-g[i]-x[i] >= 0) ins(x[i+1], min(g[i]+x[i]-t[i], x[i]));
			ins(max(x[i], x[i+1]+t[i]-t[i+1]), min(t[i]+x[i]-g[i], x[i+1]));
			if (t[i+1]-g[i]+x[i]-x[i+1] >= 0) ins(max(x[i], t[i]+x[i]-g[i]), x[i+1]); 
			ins(max(x[i], x[i+1]), min(t[i]-g[i]+x[i], t[i+1]+x[i+1]-t[i]));
			ins(max({x[i], x[i+1], t[i]-g[i]+x[i]}), floor(1.0*(t[i+1]-g[i]+x[i]+x[i+1])/2)); 
			
		}
	}
	int fl = g[n] <= t[n] || h[n]; 
	if (~gp[n]) fl = 1;  
	puts(fl ? "YES" : "NO"); 
}

signed main () {
//	freopen("t.in", "r", stdin); 
	int T = 1; 
	while (T--) solve();
	return 0;
}