Submission #66195

#	Time	Username	Problem	Language	Result	Execution time	Memory
66195		khsoo01	Can polan into space? (OJUZ11_space)	C++11	100 / 100	637 ms	122116 KiB

space

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
const ll inf = 1e18;
 
ll n, a[200005], b[200005], c[200005], sum[200005];
pair<ll,ll> dt[200005], ans;
 
vector<ll> ord;
vector<pair<ll,ll> > stk;
 
struct segtree {
	pair<ll,ll> val[888888];
	ll lazy[888888];
	void init (ll SS, ll SE, ll P) {
		if(SS == SE) {val[P] = {0, SS}; return;}
		ll mid = (SS+SE)/2;
		init(SS, mid, 2*P);
		init(mid+1, SE, 2*P+1);
		val[P] = max(val[2*P], val[2*P+1]);
	}
	void init () {init(1, n, 1);}
	void lazydown (ll P) {
		val[2*P].X += lazy[P];
		lazy[2*P] += lazy[P];
		val[2*P+1].X += lazy[P];
		lazy[2*P+1] += lazy[P];
		lazy[P] = 0;
	}
	void update (ll S, ll E, ll SS, ll SE, ll P, ll V) {
		if(S <= SS && SE <= E) {
			val[P].X += V; lazy[P] += V;
			return;
		}
		if(SE < S || E < SS) return;
		lazydown(P);
		ll mid = (SS+SE)/2;
		update(S, E, SS, mid, 2*P, V);
		update(S, E, mid+1, SE, 2*P+1, V);
		val[P] = max(val[2*P], val[2*P+1]);
	}
	void update (ll S, ll E, ll V) {update(S, E, 1, n, 1, V);}
	pair<ll,ll> query (ll S, ll E, ll SS, ll SE, ll P) {
		if(S <= SS && SE <= E) return val[P];
		if(SE < S || E < SS) return {-inf, -inf};
		lazydown(P);
		ll mid = (SS+SE)/2;
		return max(query(S, E, SS, mid, 2*P),
				   query(S, E, mid+1, SE, 2*P+1));
	}
	pair<ll,ll> query (ll S, ll E) {return query(S, E, 1, n, 1);}
} seg;
 
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		sum[i] = sum[i-1] + b[i];
	}
	seg.init();
	stk.push_back({inf, 0});
	dt[1] = {a[1], 0};
	seg.update(1, 1, dt[1].X);
	for(int i=2;i<=n;i++) {
		pair<ll,ll> tmp = max(seg.query(1, i-2), {sum[i-1], 0});
		dt[i] = {tmp.X + a[i], tmp.Y};
		ll cur = c[i] - b[i], prv = 0;
		seg.update(1, i-1, b[i]);
		while(true) {
			if(stk.back().X <= cur) {
				seg.update(stk.back().Y+1, i-1, stk.back().X - prv);
				prv = stk.back().X;
				stk.pop_back();
			}
			else {
				seg.update(stk.back().Y+1, i-1, cur - prv);
				stk.push_back({cur, i-1});
				break;
			}
		}
		seg.update(i, i, dt[i].X);
	}
	for(int i=1;i<=n;i++) {
		ans = max(ans, {dt[i].X + sum[n] - sum[i], i});
	}
	printf("%lld\n",ans.X);
	for(int i=ans.Y;i;i=dt[i].Y) ord.push_back(i);
	int i;
	for(i=ans.Y;dt[i].Y;i=dt[i].Y) {
		pair<ll, ll> tmp = {-inf, -inf};
		for(int j=dt[i].Y+1;j<i;j++) {
			tmp = max(tmp, {c[j] - b[j], j});
		}
		for(int j=dt[i].Y+1;j<tmp.Y;j++) ord.push_back(j);
		for(int j=i-1;j>=tmp.Y;j--) ord.push_back(j);
	}
	while(--i) ord.push_back(i);
	for(int i=ans.Y+1;i<=n;i++) ord.push_back(i);
	for(int i=0;i<n;i++) printf("%lld ",ord[i]);
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
space.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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