Submission #520309

#	Time	Username	Problem	Language	Result	Execution time	Memory
520309		nathanlee726	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	394 ms	53772 KiB

constellation3

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

int n,a[200010],m,rt;

struct NODE{
	int l,r,sol,sor,pa,dp;
	
}card[200010];

pii seg[800010];

pair<pii,int> b[200010];

vector<int> tv1,tv2;

vector<pii> pt[200010];

void dfs(int p){
	tv1.pb(p);
	if(card[p].sol!=-1)dfs(card[p].sol),card[p].l=card[card[p].sol].l;
	if(card[p].sor!=-1)dfs(card[p].sor),card[p].r=card[card[p].sor].r;
	tv2.pb(p);
}

void push(int p){
	seg[p*2].X+=seg[p].Y;
	seg[p*2+1].X+=seg[p].Y;
	seg[p*2].Y+=seg[p].Y;
	seg[p*2+1].Y+=seg[p].Y;
	seg[p].Y=0;
}

void modify(int p,int l,int r,int ql,int qr,int vl){
	if(l>qr||r<ql)return;
	if(l>=ql&&r<=qr){seg[p].X+=vl,seg[p].Y+=vl;return;}
	int mi=(l+r)/2;
	push(p);
	modify(p*2,l,mi,ql,qr,vl);
	modify(p*2+1,mi+1,r,ql,qr,vl);
	return;
} 

int qry(int p,int l,int r,int x){
	if(l==r)return seg[p].X;
	int mi=(l+r)/2;
	push(p);
	if(mi>=x)return qry(p*2,l,mi,x);
	else return qry(p*2+1,mi+1,r,x);
}

signed main(){
	IOS();
	int sum=0;
	cin>>n;
	F(n)cin>>a[i];
	rt=0;
	F(n){
		card[i].l=card[i].r=i;
		card[i].sol=card[i].sor=card[i].pa=-1;
		card[i].dp=0;
		if(i!=0){
			int p=i-1,pp=-2;
			while(p!=-1){
				if(a[i]>a[p]){pp=p,p=card[p].pa;}
				else break;
				
			}
			if(p!=-1){
				if(pp!=-2){
					card[p].sor=i;
					card[i].pa=p;
					card[i].sol=pp;
					card[pp].pa=i;	
				}
				else{
					card[p].sor=i;
					card[i].pa=p;
				}
			}
			else{
				rt=i;
				assert(pp!=-2);
				card[i].sol=pp;
				card[pp].pa=i;
			}
		}	
	}
	dfs(rt);
	cin>>m;
	F(m){
		cin>>b[i].X.X>>b[i].X.Y>>b[i].Y;
		b[i].X.X--;sum+=b[i].Y;
	}
	sort(b,b+m);
	vector<int> tv;
	vector<pair<int,pii> > qu;
	int p=0;
	while(p<n&&card[tv1[p]].l==0)tv.pb(tv1[p++]);
	qu.pb({tv[0],{n,a[tv[0]]+1}});
	F(sz(tv)-1)qu.pb({tv[i+1],{a[tv[i]],a[tv[i+1]]+1}});
	F(m){
		while(sz(qu)&&card[qu.back().X].r<b[i].X.X)qu.pop_back();
		while(p<n){
			if(card[tv1[p]].l>b[i].X.X)break;
			if(card[tv1[p]].l<=b[i].X.X&&card[tv1[p]].r>=b[i].X.X)qu.pb({tv1[p],{qu.back().Y.Y-1,a[tv1[p]]+1}});
			p++;
		}	
		int tl=0,tr=sz(qu)-1;
		while(tl<tr){
			int mi=(tl+tr)/2;
			if(qu[mi].Y.Y<=b[i].X.Y)tr=mi;
			else tl=mi+1;
		}
		pt[qu[tl].X].pb({b[i].X.X,b[i].Y});
	}
	for(int i:tv2){
		int vll,vlr;
		if(card[i].sol!=-1)vll=card[card[i].sol].dp;
		else vll=0;
		if(card[i].sor!=-1)vlr=card[card[i].sor].dp;
		else vlr=0;
		int tans=vll+vlr;
		for(auto pi:pt[i]){
			if(pi.X==i){
				tans=max(tans,vll+vlr+pi.Y);
			}
			else if(pi.X<i){
				tans=max(tans,qry(1,0,n-1,pi.X)+vlr+pi.Y);
			}
			else{
				tans=max(tans,qry(1,0,n-1,pi.X)+vll+pi.Y);
			}
		}
		card[i].dp=tans;
		if(card[i].sol!=-1)modify(1,0,n-1,card[card[i].sol].l,card[card[i].sol].r,vlr);
		if(card[i].sor!=-1)modify(1,0,n-1,card[card[i].sor].l,card[card[i].sor].r,vll);
		modify(1,0,n-1,i,i,vll+vlr);
	}
	F(n){
		bug(i,card[i].pa,card[i].l,card[i].r,card[i].sol,card[i].sor,card[i].dp,sz(pt[i]));
	}
	cout<<sum-card[rt].dp<<endl;
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65