제출 #20368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20368		admin	Can polan into space? (OJUZ11_space)	C++14	0 / 100	387 ms	33040 KiB

space

#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
 
int N;
const int MAX_N = 200010;
 
ll a[MAX_N][3],sum[MAX_N][3];
 
vector<int> pmax_id;
 
struct mem{
	ll c,v,id;
	mem(){}
	mem(ll c_,ll v_,ll id_):c(c_),v(v_),id(id_){}
	bool operator<(const mem& r)const{
		return c<r.c;
	}
}tree[MAX_N*4],dp[MAX_N];
ll add[MAX_N*4];
 
#define LL (2*k+1)
#define RR (2*k+2)
 
void make(int s,int e,int k){
	if(s==e){
		tree[k]=mem(-1e15,s,0);
		return;
	}
	int mid=(s+e)/2;
	make(s,mid,LL);
	make(mid+1,e,RR);
}
 
void up(int k){
	tree[k]=max(tree[LL],tree[RR]);
}
 
void down(int k){
	tree[LL].c+=add[k];
	tree[RR].c+=add[k];
	add[LL]+=add[k];
	add[RR]+=add[k];
	add[k]=0;
}
 
void addRange(int s,int e,int L,int R,int c,int k){
	if(s>R||e<L)return;
	if(L<=s&&e<=R){
		add[k]+=c;
		tree[k].c+=c;
		return;
	}
	down(k);
 
	int mid=(s+e)/2;
	addRange(s,mid,L,R,c,LL);
	addRange(mid+1,e,L,R,c,RR);
	up(k);
}
 
void update(int s,int e,int x,int c,int k){
	if(s==e){
		tree[k].c=c;
		tree[k].v=s;
		return;
	}
	down(k);
 
	int mid=(s+e)/2;
	if(x<=mid)update(s,mid,x,c,LL);
	else update(mid+1,e,x,c,RR);
	up(k);
}
 
mem query(int s,int e,int L,int R,int k){
	if(s>R||e<L)return mem(-1e15,0,0);
	if(L<=s&&e<=R){
		return tree[k];
	}
	int mid=(s+e)/2;
	return max(query(s,mid,L,R,LL),query(mid+1,e,L,R,RR));
}
 
int getPos(int x){
	int lo=0,hi=pmax_id.size()-1,mid;
	while(lo+1<hi){
		mid=(lo+hi)/2;
		if(pmax_id[mid]<=x)lo=mid;
		else hi=mid;
	}
	if(pmax_id[lo]>x)return pmax_id[lo];
	return pmax_id[hi];
}
 
void f(int x,vector<int>& s){
	if(x==0)return;
	f(dp[x].v,s);
	s.push_back(x);
}
 
int main(){
	
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		for(int j=0;j<3;j++){
			scanf("%lld",&a[i][j]);
			sum[i][j]+=sum[i-1][j]+a[i][j];
		}
	}
 
	make(1,N,0);
 
	for(int i=1;i<=N;i++){
		dp[i]=mem(sum[i-1][1]+a[i][0],0,0);
		int sz=pmax_id.size();
		while(sz>1&&a[pmax_id[sz-1]][2]-a[pmax_id[sz-1]][1]<a[i-1][2]-a[i-1][1]){
			ll pre_max=a[pmax_id[sz-1]][2]-a[pmax_id[sz-1]][1];
			ll cur_max=a[i-1][2]-a[i-1][1];
			addRange(1,N,pmax_id[sz-2],pmax_id[sz-1]-1,cur_max-pre_max,0);
			pmax_id.pop_back();sz--;
		}
		pmax_id.push_back(i-1);
/*
		for(int j=1;j<=i-2;j++){
			mem t = query(1,N,j,j,0);
			printf("(%lld,%lld,%lld) ",t.c,t.v,t.id);
		}printf("   :   ");
*/
		mem dp_j = query(1,N,1,i-2,0);
//		printf("%lld  -->  ",dp_j+a[i][0]-a[i][1]+sum[i][1]);
 
		if(dp[i].c<dp_j.c+a[i][0]-a[i][1]+sum[i][1]){
			dp[i].c=dp_j.c+a[i][0]-a[i][1]+sum[i][1];
			dp[i].v=dp_j.v;
			dp[i].id=getPos(dp_j.v);
		}
 
//		printf("(%lld,%lld,%lld)\n",dp[i].c,dp[i].v,dp[i].id);
 
		update(1,N,i,dp[i].c-sum[i][1]+a[i+1][2]-a[i+1][1],0);
	}
 
 
	ll ans=0,v;
	for(int i=1;i<=N;i++){
		if(ans<dp[i].c+sum[N][1]-sum[i][1]){
			ans=dp[i].c+sum[N][1]-sum[i][1];
			v=i;
		}
	}
 
	printf("%lld\n",ans);
 
	vector<int> st;
	f(v,st);
 
	assert(!st.empty());
 
	for(int i=0;i<st.size();i++){
		printf("%d ",st[i]);
	}
 
	for(int i=st.front()-1;i>=1;i--)printf("%d ",i);
	for(int i=st.back()+1;i<=N;i++)printf("%d ",i);
	
	for(int i=1;i<st.size();i++){
		for(int j=st[i-1]+1;j<dp[st[i]].id;j++)printf("%d ",j);
		for(int j=st[i]-1;j>=dp[st[i]].id;j--)printf("%d ",j);
	}
	puts("");
 
	return 0;
}

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

space.cpp: In function 'int main()':
space.cpp:165:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<st.size();i++){
               ^
space.cpp:172:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<st.size();i++){
               ^
space.cpp:109:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
space.cpp:112:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&a[i][j]);
                          ^
space.cpp:161:3: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  f(v,st);
   ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 26
• Subtask 5: 0 / 28