Submission #444805

#	Time	Username	Problem	Language	Result	Execution time	Memory
444805		kig9981	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	636 ms	79068 KiB

constellation3

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int SZ=1<<18;
vector<int> adj[200002], U[200002], P;
vector<pair<int,int>> Q[200002];
int node_cnt, L[200002][18], R[200002][18], A[200002], numL[200002], numR[200002], LR[200002], RR[200002], tree[2*SZ];
long long Ltree[200003], Rtree[200003], LD[200002], RD[200002];

void set_tree(int n, int v) {for(tree[n+=SZ]=v;n>>=1;) tree[n]=max(tree[2*n],tree[2*n+1]);}
void add_tree(long long *tree, int n, long long v) {for(;n<200003;n+=n&-n) tree[n]+=v;}
void add_tree(long long *tree, int s, int e, long long v) {add_tree(tree,s,v); add_tree(tree,e+1,-v);}

void dfs(int c, int *num, int *R)
{
	num[c]=++node_cnt;
	for(auto n: adj[c]) dfs(n,num,R);
	R[c]=node_cnt;
}

int get_lpos(int v)
{
	int bit=1, s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(tree[2*bit+1]>=v) tie(bit,s)=make_pair(2*bit+1,m+1);
		else tie(bit,e)=make_pair(2*bit,m);
	}
	return s;
}

int get_rpos(int v)
{
	int bit=1, s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(tree[2*bit]>=v) tie(bit,e)=make_pair(2*bit,m);
		else tie(bit,s)=make_pair(2*bit+1,m+1);
	}
	return s;
}

int get_max(int s, int e)
{
	int ret=-1;
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret=max(ret,tree[s++]);
		if(~e&1) ret=max(ret,tree[e--]);
	}
	return ret;
}

void get_mp(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(n2<n1 || n2<s || e<n1 || tree[bit]<v) return;
	if(s==e) {
		P.push_back(m);
		return;
	}
	get_mp(n1,n2,v,2*bit,s,m);
	get_mp(n1,n2,v,2*bit+1,m+1,e);
}

long long get_sum(long long *tree, int n)
{
	long long ret=0;
	for(;n;n-=n&-n) ret+=tree[n];
	return ret;
}

long long get_LD(int x)
{
	if(R[x][0]-x<2) return LD[x];
	long long temp=0; P.clear();
	get_mp(x+1,R[x][0]-1,get_max(x+1,R[x][0]-1));
	temp=RD[P[0]];
	for(auto p: P) temp+=LD[p];
	return LD[x]=min(LD[x],temp);
}

long long get_RD(int x)
{
	if(x-L[x][0]<2) return RD[x];
	long long temp=0; P.clear();
	get_mp(L[x][0]+1,x-1,get_max(L[x][0]+1,x-1));
	temp=RD[P[0]];
	for(auto p: P) temp+=LD[p];
	return RD[x]=min(RD[x],temp);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	long long S=0;
	cin>>N; A[0]=A[N+1]=0x7fffffff;
	for(int i=1;i<=N;i++) {
		cin>>A[i];
		U[A[i]].push_back(i);
	}
	cin>>M;
	for(int i=0;i<M;i++) {
		int x, y, c;
		cin>>x>>y>>c;
		Q[y].emplace_back(x,c);
		S+=c;
	}
	set_tree(0,A[0]);
	for(int i=0;++i<=N;) {
		adj[L[i][0]=get_lpos(A[i])].push_back(i);
		set_tree(i,A[i]);
	}
	dfs(0,numL,LR); numL[N+1]=LR[N+1]=++node_cnt;
	memset(tree,0,sizeof(tree));
	set_tree(N+1,A[0]); R[N+1][0]=N+1;
	for(int i=N+1;--i;) {
		adj[R[i][0]=get_rpos(A[i])].push_back(i);
		adj[i].clear();
		set_tree(i,A[i]);
	}
	set_tree(0,A[0]);
	node_cnt=0; dfs(N+1,numR,RR); numR[0]=RR[0]=++node_cnt;
	R[0][0]=N+1; L[N+1][0]=0;
	for(int j=1;j<18;j++) for(int i=N+2;--i>=0;) {
		L[i][j]=L[L[i][j-1]][j-1];
		R[i][j]=R[R[i][j-1]][j-1];
	}
	for(int y=0;++y<=N;) {
		for(auto[x,c]: Q[y]) {
			int l=x, r=x;
			long long v;
			for(int j=18;--j>=0;) {
				if(A[L[l][j]]<y) l=L[l][j];
				if(A[R[r][j]]<y) r=R[r][j];
			}
			l=L[l][0]; r=R[r][0];
			v=get_sum(Ltree,numL[x])+get_sum(Rtree,numR[x])-c;
			LD[l]=min(LD[l],v); RD[r]=min(RD[r],v);
		}
		for(auto x: U[y]) {
			add_tree(Ltree,numL[x],LR[x],get_RD(x));
			add_tree(Rtree,numR[x],RR[x],get_LD(x));
		}
	}
	cout<<S+get_LD(0)<<'\n';
	return 0;
}

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