제출 #1144047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144047		jiahng	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	1065 ms	129596 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef pair<ll,ll> pill;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
typedef pair <pi,pi> pipi;
#define maxn 500010

int N;
int discX[maxn],E[maxn],A[maxn];
pi X[maxn]; vi v;

struct node{
	int s,e,m;
	pi val1,val2;
	node *l=nullptr,*r=nullptr;
	
	node(int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
		
		if (s != e){
			l = new node(s,m); r = new node(m+1,e);
			val1 = min(l->val1, r->val1);
			val2 = min(l->val2, r->val2);
		}else{
			val1 = pi(A[s] - v[s-1],s);
			val2 = pi(A[s] + v[s-1],s);
		}
	}
	void upd(int p){
		if (s == e){
			val1 = val2 = pi(INF,INF); return;
		}else if (p > m) r->upd(p);
		else l->upd(p);
		val1 = min(l->val1, r->val1);
		val2 = min(l->val2, r->val2);
	}
	pi qry(int a,int b,int t){
		if (a > b) return pi(INF,INF);
		if (a <= s && e <= b) return (t == 1 ? val1 : val2);
		else if (a > e || s > b) return pi(INF,INF);
		else return min(l->qry(a,b,t), r->qry(a,b,t));
	}
}*root;

int32_t main(){
	fast;
	cin >> N;
	FOR(i,1,N) cin >> X[i].f >> X[i].s;
	sort(X+1,X+N+1);

	FOR(i,1,N) v.pb(X[i].f);
	v.erase(unique(all(v)), v.end());
	FOR(i,1,N){
		discX[i] = lbd(v, X[i].f) - v.begin() + 1;
		A[discX[i]] = max(A[discX[i]], X[i].s);
	}
	
	int M = v.size();
	set <pi> left;
	FOR(i,1,M) left.insert(pi(A[i], i));
	root = new node(1,M);
	int ans = 0;
	while (!left.empty()){
		pi cur = *left.rbegin();
		//~ cerr << cur.f << ' ' << cur.s << '\n';
		while (root->qry(1,cur.s,1).f <= cur.f - v[cur.s-1]){
			pi x = root->qry(1,cur.s,1);
			//~ cerr << x.s << ' ';
			assert(left.find(pi(A[x.s], x.s)) != left.end());
			left.erase(pi(A[x.s], x.s));
			root->upd(x.s);
		}
		//~ cerr << '\n';
		while (root->qry(cur.s+1,M,2).f <= cur.f + v[cur.s-1]){
			pi x = root->qry(cur.s+1,M,2);
			//~ cerr << x.s << ' ';
			assert(left.find(pi(A[x.s], x.s)) != left.end());
			left.erase(pi(A[x.s], x.s));
			root->upd(x.s);
		}
		//~ cerr << "\n\n";
		ans++;
	}
	cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31