Submission #1174580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174580		jiahng	Bouquet (EGOI24_bouquet)	C++20	8 / 100	228 ms	266244 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 998244353
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
typedef pair <pi,pi> pipi;
#define maxn 500010
int TC;
int N,L[maxn],R[maxn],dp[maxn];
struct node{
	int s,e,m,val=0;
	node *l,*r;
	node(int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
		
	}
	void create(){
		if (s != e){
			l = new node(s,m); r = new node(m+1,e);
			l->create(); r->create();
		}
	}
	int qry(int a,int b){
		if (a <= s && e <= b) return val;
		else if (a > e || s > b) return 0;
		return max(l->qry(a,b), r->qry(a,b));
	}
	void upd(int p,int v, node *ref){
		if (s == e){
			val = max(ref->val, v);
			return;
		}
		if (p > m){
			l = ref->l;
			r = new node(m+1,e);
			r->upd(p,v,ref->r);
		}else{
			r = ref->r;
			l = new node(s,m);
			l->upd(p,v,ref->l);
		}
		
		val = max(l->val, r->val);
	
	}
}*root;
int32_t main(){
	fast;
	cin >> N;
	FOR(i,1,N){
		cin >> L[i] >> R[i];
	}
	deque <node*> roots;
	roots.pb(new node(1,N));
	roots.back()->create();
	int ans = 0;
	DEC(i,N,1){
		int dp = roots[min(R[i], (int)roots.size()-1)]->qry(i,N)+1;
		node* nroot = new node(1,N);
		nroot->upd(i-L[i]-1,dp , roots[0]);
		roots.push_front(nroot);
		ans = max(ans, dp);
	}
	cout << ans;
	
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 16
• Subtask 3: 0 / 28
• Subtask 4: 0 / 18
• Subtask 5: 0 / 30