제출 #213061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
213061		Pajaraja	별자리 3 (JOI20_constellation3)	C++17	100 / 100	673 ms	86776 KiB

constellation3

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
long long dp[MAXN],seg[4*MAXN];
int lc[40*MAXN],per[40*MAXN],mxb[MAXN],mnb[MAXN],rc[40*MAXN],dl[MAXN],dr[MAXN],h[MAXN],root[MAXN],cnt,n,m;
struct star{int x,y; long long c;};
bool cmp(star a,star b) {return a.y<b.y;}
star a[MAXN];
vector<int> zp[MAXN],zf[MAXN];
void updmxb(int x,int ind)
{
	while(ind<MAXN) 
	{
		mxb[ind]=max(mxb[ind],x); 
		ind+=(ind&-ind);
	}
}
int nmax(int ind)
{
	int val=0;
	while(ind)
	{
		val=max(val,mxb[ind]);
		ind-=(ind&-ind);
	}
	return val;
}
void updmnb(int x,int ind)
{
	while(ind<MAXN) 
	{
		mnb[ind]=min(mnb[ind],x); 
		ind+=ind&-ind;
	}
}
int nmin(int ind)
{
	int val=MAXN;
	while(ind)
	{
		val=min(val,mnb[ind]);
		ind-=(ind&-ind);
	}
	return val;
}
void updseg(int l,int r,int lt,int rt,long long v,int ind)
{
	if(r<lt || l>rt) return;
	if(l>=lt && r<=rt) {seg[ind]+=v; return;}
	int s=(l+r)/2;
	updseg(l,s,lt,rt,v,2*ind);
	updseg(s+1,r,lt,rt,v,2*ind+1);
}
long long nsum(int l,int r,int t,int ind)
{
	if(l==r) return seg[ind];
	int s=(l+r)/2;
	if(s>=t) return seg[ind]+nsum(l,s,t,2*ind);
	return seg[ind]+nsum(s+1,r,t,2*ind+1);
}
void makeper(int l,int r,int ind)
{
	per[ind]=m+1;
	if(l==r) return;
	int s=(l+r)/2;
	lc[ind]=++cnt;
	makeper(l,s,lc[ind]);
	rc[ind]=++cnt;
	makeper(s+1,r,rc[ind]);
}
void makenewper(int l,int r,int t,int val,int inh,int ind)
{
	per[ind]=val;
	if(l==r) return;
	int s=(l+r)/2;
	if(t<=s)
	{
		rc[ind]=rc[inh];
		lc[ind]=++cnt;
		makenewper(l,s,t,val,lc[inh],lc[ind]);
	}
	else
	{
		lc[ind]=lc[inh];
		rc[ind]=++cnt;
		makenewper(s+1,r,t,val,rc[inh],rc[ind]);
	}
}
int fnd(int l,int r,int lt,int rt,int ind)
{
	if(r<lt || l>rt) return MAXN;
	if(l>=lt && r<=rt) return per[ind];
	int s=(l+r)/2;
	return min(fnd(l,s,lt,rt,lc[ind]),fnd(s+1,r,lt,rt,rc[ind]));
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].c);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++) zf[a[i].x].push_back(i);
	fill(mnb,mnb+MAXN,n+1);
	for(int i=1;i<=n;i++)
	{
		updmxb(i,n+1-h[i]);
		for(int j=0;j<zf[i].size();j++) dl[zf[i][j]]=nmax(n+1-a[zf[i][j]].y);
	}
	for(int i=n;i>=1;i--)
	{
		updmnb(i,n+1-h[i]);
		for(int j=0;j<zf[i].size();j++) dr[zf[i][j]]=nmin(n+1-a[zf[i][j]].y);
	}
	makeper(1,n,root[m+1]);
	for(int i=m;i>=1;i--)
	{
		root[i]=++cnt;
		makenewper(1,n,a[i].x,i,root[i+1],root[i]);
	}
	a[m+1].c=0;
	for(int i=1;i<=m+1;i++)
	{
		long long nc=nsum(1,n,a[i].x,1),ac=a[i].c;
		for(int j=0;j<zp[i].size();j++) {nc+=dp[zp[i][j]]; ac+=dp[zp[i][j]];}
		dp[i]=min(ac,nc);
		if(i==m+1) continue;
		int nxt=fnd(1,n,dl[i]+1,dr[i]-1,root[i+1]);
		zp[nxt].push_back(i);
		updseg(1,n,dl[i]+1,dr[i]-1,ac-dp[i],1);
	}
	printf("%lld",dp[m+1]);
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main()':
constellation3.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<zf[i].size();j++) dl[zf[i][j]]=nmax(n+1-a[zf[i][j]].y);
               ~^~~~~~~~~~~~~
constellation3.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<zf[i].size();j++) dr[zf[i][j]]=nmin(n+1-a[zf[i][j]].y);
               ~^~~~~~~~~~~~~
constellation3.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<zp[i].size();j++) {nc+=dp[zp[i][j]]; ac+=dp[zp[i][j]];}
               ~^~~~~~~~~~~~~
constellation3.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
constellation3.cpp:99:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&h[i]);
                        ~~~~~^~~~~~~~~~~~
constellation3.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
constellation3.cpp:101:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].c);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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