Submission #222488

#	Time	Username	Problem	Language	Result	Execution time	Memory
222488		haojiandan	Constellation 3 (JOI20_constellation3)	C++11	100 / 100	985 ms	131960 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(4e5)+10;
const int INF=(1e6);
int n,m,tot,a[maxn],rt,fa[maxn];
int L[maxn],R[maxn],p[maxn],back[maxn];
ll f[maxn],g[maxn],tmp;
vector<int> son[maxn];
struct star { int x,y,c; } d[maxn];
map<pair<int,int>,int> dy;
vector<int> G[maxn]; // stars in this region
ll sum[maxn];
int dfn[maxn],Son[maxn],sz[maxn],cnt,top[maxn];
namespace Seg1 {
	int st[maxn][20],lg[maxn],pos[maxn][20],mn[maxn][20]; // mx -> first in the left & right >= me
	int Querymx(int l,int r) {
		int j=lg[r-l+1];
		int x=st[l][j],y=st[r-(1<<j)+1][j];
		return max(x,y);
	}
	int querymx(int l,int r) {
		int j=lg[r-l+1];
		int x=pos[l][j],y=pos[r-(1<<j)+1][j];
		if (a[x]>=a[y]) return x;
		return y;
	}
	int Querymn(int l,int r) {
		int j=lg[r-l+1];
		int x=mn[l][j],y=mn[r-(1<<j)+1][j];
		return min(x,y);
	}
	void init() {
		int x,y;
		for (int i=0;i<=n+1;i++) st[i][0]=mn[i][0]=a[i],pos[i][0]=i;
		for (int i=2;i<=n+2;i++) lg[i]=lg[i/2]+1;
		for (int j=1;j<=19;j++)
		for (int i=0;i+(1<<j)-1<=n+1;i++) {
			x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
			st[i][j]=max(x,y);
			x=pos[i][j-1],y=pos[i+(1<<(j-1))][j-1];
			if (a[x]>=a[y]) pos[i][j]=x;
			else pos[i][j]=y;
			x=mn[i][j-1],y=mn[i+(1<<(j-1))][j-1];
			mn[i][j]=min(x,y);
		}
	}
	void solve() {
		int l,r,mid,res,x,y;
		for (int i=1;i<=m;i++) {
			l=0,r=d[i].x-1; res=0;
			while (l<=r) {
				mid=(l+r)/2;
				if (Querymx(mid,d[i].x-1)>=d[i].y) l=mid+1,res=mid;
				else r=mid-1;
			}
			x=res+1;
			l=d[i].x+1,r=n+1; res=0;
			while (l<=r) {
				mid=(l+r)/2;
				if (Querymx(d[i].x+1,mid)>=d[i].y) r=mid-1,res=mid;
				else l=mid+1;
			}
			y=res-1;
			//printf("find id=%d l=%d r=%d\n",i,x,y);
			x=dy[make_pair(x,y)];
			sum[x]+=d[i].c;
			G[x].push_back(i);
		}
	}
};
namespace Seg2 {
	int tr[maxn*4],lazy[maxn*4]; // mx -> belong to the deepest node
	void pushdown(int root) {
		if (!lazy[root]) return;
		tr[root*2]=max(tr[root*2],lazy[root]);
		tr[root*2+1]=max(tr[root*2+1],lazy[root]);
		lazy[root*2]=max(lazy[root*2],lazy[root]);
		lazy[root*2+1]=max(lazy[root*2+1],lazy[root]);
		lazy[root]=0;
	}
	void add(int L,int R,int l,int r,int root,int delta) {
		if (L<=l&&r<=R) {
			tr[root]=max(tr[root],delta);
			lazy[root]=max(lazy[root],delta);
			return;
		}
		pushdown(root);
		int mid=(l+r)/2;
		if (L<=mid) add(L,R,l,mid,root*2,delta);
		if (mid<R) add(L,R,mid+1,r,root*2+1,delta);
		tr[root]=max(tr[root*2],tr[root*2+1]);
	}
	int query(int x,int l,int r,int root) {
		if (l==r) return tr[root];
		pushdown(root);
		int mid=(l+r)/2;
		if (x<=mid) return query(x,l,mid,root*2);
		return query(x,mid+1,r,root*2+1);
	}
};
int build(int l,int r) {
	tot++;
	dy[make_pair(l,r)]=tot;
	L[tot]=l,R[tot]=r;
	int u=tot,mx=Seg1::Querymx(l,r),mn=Seg1::Querymn(l,r);
	if (mn==mx) return u;
	int x=Seg1::querymx(l,r),y;
	if (l<=x-1) son[u].push_back(build(l,x-1));
	while (x<=r) {
		y=Seg1::querymx(x+1,r);
		if (a[y]==mx) {
			if (x+1<=y-1) son[u].push_back(build(x+1,y-1));
			x=y;
		} else {
			if (x+1<=r) son[u].push_back(build(x+1,r));
			break;
		}
	}
	return u;
}
void dfs(int u) {
	sz[u]=1;
	for (int i=0,v;i<son[u].size();i++) {
		v=son[u][i];
		dfs(v);
		fa[v]=u;
		sz[u]+=sz[v];
		if (sz[v]>sz[Son[u]]) Son[u]=v;
	}
}
void dfs(int u,int t) {
	dfn[u]=++cnt; back[cnt]=u;
	top[u]=t;
	Seg2::add(L[u],R[u],1,n,1,dfn[u]);
	if (Son[u]) dfs(Son[u],t);
	for (int i=0,v;i<son[u].size();i++) {
		v=son[u][i];
		if (v==Son[u]) continue;
		dfs(v,v);
	}
}
namespace Seg3 {
	ll tr[maxn]; // sum -> DP
	void add(int x,ll delta) {
		x=dfn[x];
		for (;x<=tot;x+=x&(-x)) tr[x]+=delta;
	}
	ll query(int x) {
		ll res=0;
		for (;x;x-=x&(-x)) res+=tr[x];
		return res;
	}
	ll Query(int l,int r) {
		return query(r)-query(l-1);
	}
	ll query(int x,int y) {
		if (x==y) return 0;
		ll res=0;
		while (top[x]!=top[y]) {
			res+=Query(dfn[top[x]],dfn[x]);
			x=fa[top[x]];
		}
		if (x==y) return res;
		return res+Query(dfn[y]+1,dfn[x]);
	}
};
void solve(int u) {
	f[u]=sum[u];
	for (int i=0,v;i<son[u].size();i++) {
		v=son[u][i];
		solve(v);
		f[u]+=f[v];
	}
	ll first=f[u];
	for (int i=0;i<G[u].size();i++) {
		tmp=first-d[G[u][i]].c+Seg3::query(p[d[G[u][i]].x],u);
		f[u]=min(f[u],tmp);
	}
	g[u]=first-f[u];
//	printf("dp[%d]: %lld %lld %lld\n",u,first,f[u],g[u]);
	Seg3::add(u,g[u]);
}
int main() {
	//freopen("1.txt","r",stdin);
	int x,y;
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	read(m);
	for (int i=1;i<=m;i++) read(d[i].x),read(d[i].y),read(d[i].c);
	a[0]=a[n+1]=INF;
	Seg1::init();
	rt=build(1,n);
	Seg1::solve();
	dfs(rt);
	dfs(rt,rt);
	for (int i=1;i<=n;i++) {
		p[i]=back[Seg2::query(i,1,n,1)];//,printf("p[%d]=%d\n",i,p[i]);
	}
	solve(rt);
	printf("%lld\n",f[rt]);
	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'void dfs(int)':
constellation3.cpp:129:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0,v;i<son[u].size();i++) {
                 ~^~~~~~~~~~~~~~
constellation3.cpp: In function 'void dfs(int, int)':
constellation3.cpp:142:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0,v;i<son[u].size();i++) {
                 ~^~~~~~~~~~~~~~
constellation3.cpp: In function 'void solve(int)':
constellation3.cpp:175:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0,v;i<son[u].size();i++) {
                 ~^~~~~~~~~~~~~~
constellation3.cpp:181:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<G[u].size();i++) {
               ~^~~~~~~~~~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:191:6: warning: unused variable 'x' [-Wunused-variable]
  int x,y;
      ^
constellation3.cpp:191:8: warning: unused variable 'y' [-Wunused-variable]
  int x,y;
        ^

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