Submission #20463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20463	2017-02-11T23:50:37 Z	책상다리황새두렁넘기(#60, khsoo01)	Can polan into space? (OJUZ11_space)	C++11	0 / 100	389 ms	35408 KB

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 + b[n] - b[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

space.cpp: In function 'int main()':
space.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
space.cpp:61:42: 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
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	32248 KB	Output is correct
2	Incorrect	0 ms	32248 KB	Output isn't correct
3	Correct	0 ms	32248 KB	Output is correct
4	Incorrect	0 ms	32248 KB	Output isn't correct
5	Incorrect	0 ms	32248 KB	Output isn't correct
6	Incorrect	0 ms	32248 KB	Output isn't correct
7	Incorrect	0 ms	32248 KB	Output isn't correct
8	Incorrect	3 ms	32248 KB	Output isn't correct
9	Correct	0 ms	32248 KB	Output is correct
10	Correct	0 ms	32248 KB	Output is correct
11	Correct	0 ms	32248 KB	Output is correct
12	Correct	0 ms	32248 KB	Output is correct
13	Incorrect	3 ms	32248 KB	Output isn't correct
14	Correct	0 ms	32248 KB	Output is correct
15	Incorrect	3 ms	32248 KB	Output isn't correct
16	Correct	0 ms	32248 KB	Output is correct
17	Correct	3 ms	32248 KB	Output is correct
18	Correct	0 ms	32248 KB	Output is correct
19	Correct	0 ms	32248 KB	Output is correct
20	Correct	6 ms	32248 KB	Output is correct
21	Correct	0 ms	32248 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	32248 KB	Output is correct
2	Incorrect	0 ms	32248 KB	Output isn't correct
3	Correct	0 ms	32248 KB	Output is correct
4	Incorrect	0 ms	32248 KB	Output isn't correct
5	Incorrect	0 ms	32248 KB	Output isn't correct
6	Incorrect	0 ms	32248 KB	Output isn't correct
7	Incorrect	0 ms	32248 KB	Output isn't correct
8	Incorrect	3 ms	32248 KB	Output isn't correct
9	Correct	0 ms	32248 KB	Output is correct
10	Correct	0 ms	32248 KB	Output is correct
11	Correct	0 ms	32248 KB	Output is correct
12	Correct	0 ms	32248 KB	Output is correct
13	Incorrect	3 ms	32248 KB	Output isn't correct
14	Correct	0 ms	32248 KB	Output is correct
15	Incorrect	3 ms	32248 KB	Output isn't correct
16	Correct	0 ms	32248 KB	Output is correct
17	Correct	3 ms	32248 KB	Output is correct
18	Correct	0 ms	32248 KB	Output is correct
19	Correct	0 ms	32248 KB	Output is correct
20	Correct	6 ms	32248 KB	Output is correct
21	Correct	0 ms	32248 KB	Output is correct
22	Incorrect	0 ms	32248 KB	Output isn't correct
23	Incorrect	0 ms	32248 KB	Output isn't correct
24	Incorrect	0 ms	32248 KB	Output isn't correct
25	Incorrect	0 ms	32248 KB	Output isn't correct
26	Correct	0 ms	32248 KB	Output is correct
27	Incorrect	0 ms	32248 KB	Output isn't correct
28	Correct	0 ms	32248 KB	Output is correct
29	Correct	3 ms	32248 KB	Output is correct
30	Incorrect	0 ms	32248 KB	Output isn't correct
31	Correct	3 ms	32248 KB	Output is correct
32	Correct	0 ms	32248 KB	Output is correct
33	Incorrect	0 ms	32248 KB	Output isn't correct
34	Incorrect	3 ms	32248 KB	Output isn't correct
35	Correct	0 ms	32248 KB	Output is correct
36	Correct	3 ms	32248 KB	Output is correct
37	Correct	6 ms	32248 KB	Output is correct

Subtask #3
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	32248 KB	Output is correct
2	Incorrect	0 ms	32248 KB	Output isn't correct
3	Correct	0 ms	32248 KB	Output is correct
4	Incorrect	0 ms	32248 KB	Output isn't correct
5	Incorrect	0 ms	32248 KB	Output isn't correct
6	Incorrect	0 ms	32248 KB	Output isn't correct
7	Incorrect	0 ms	32248 KB	Output isn't correct
8	Incorrect	3 ms	32248 KB	Output isn't correct
9	Correct	0 ms	32248 KB	Output is correct
10	Correct	0 ms	32248 KB	Output is correct
11	Correct	0 ms	32248 KB	Output is correct
12	Correct	0 ms	32248 KB	Output is correct
13	Incorrect	3 ms	32248 KB	Output isn't correct
14	Correct	0 ms	32248 KB	Output is correct
15	Incorrect	3 ms	32248 KB	Output isn't correct
16	Correct	0 ms	32248 KB	Output is correct
17	Correct	3 ms	32248 KB	Output is correct
18	Correct	0 ms	32248 KB	Output is correct
19	Correct	0 ms	32248 KB	Output is correct
20	Correct	6 ms	32248 KB	Output is correct
21	Correct	0 ms	32248 KB	Output is correct
22	Incorrect	0 ms	32248 KB	Output isn't correct
23	Incorrect	0 ms	32248 KB	Output isn't correct
24	Incorrect	0 ms	32248 KB	Output isn't correct
25	Incorrect	0 ms	32248 KB	Output isn't correct
26	Correct	0 ms	32248 KB	Output is correct
27	Incorrect	0 ms	32248 KB	Output isn't correct
28	Correct	0 ms	32248 KB	Output is correct
29	Correct	3 ms	32248 KB	Output is correct
30	Incorrect	0 ms	32248 KB	Output isn't correct
31	Correct	3 ms	32248 KB	Output is correct
32	Correct	0 ms	32248 KB	Output is correct
33	Incorrect	0 ms	32248 KB	Output isn't correct
34	Incorrect	3 ms	32248 KB	Output isn't correct
35	Correct	0 ms	32248 KB	Output is correct
36	Correct	3 ms	32248 KB	Output is correct
37	Correct	6 ms	32248 KB	Output is correct
38	Incorrect	6 ms	32248 KB	Output isn't correct
39	Incorrect	0 ms	32248 KB	Output isn't correct
40	Correct	0 ms	32248 KB	Output is correct
41	Correct	0 ms	32248 KB	Output is correct
42	Incorrect	0 ms	32248 KB	Output isn't correct
43	Correct	3 ms	32248 KB	Output is correct
44	Correct	0 ms	32248 KB	Output is correct
45	Incorrect	3 ms	32248 KB	Output isn't correct
46	Incorrect	0 ms	32248 KB	Output isn't correct
47	Incorrect	0 ms	32248 KB	Output isn't correct
48	Incorrect	0 ms	32248 KB	Output isn't correct
49	Incorrect	0 ms	32248 KB	Output isn't correct
50	Incorrect	0 ms	32248 KB	Output isn't correct
51	Correct	0 ms	32248 KB	Output is correct
52	Correct	3 ms	32248 KB	Output is correct
53	Correct	3 ms	32248 KB	Output is correct

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	32248 KB	Output is correct
2	Incorrect	0 ms	32248 KB	Output isn't correct
3	Correct	0 ms	32248 KB	Output is correct
4	Incorrect	0 ms	32248 KB	Output isn't correct
5	Incorrect	0 ms	32248 KB	Output isn't correct
6	Incorrect	0 ms	32248 KB	Output isn't correct
7	Incorrect	0 ms	32248 KB	Output isn't correct
8	Incorrect	3 ms	32248 KB	Output isn't correct
9	Correct	0 ms	32248 KB	Output is correct
10	Correct	0 ms	32248 KB	Output is correct
11	Correct	0 ms	32248 KB	Output is correct
12	Correct	0 ms	32248 KB	Output is correct
13	Incorrect	3 ms	32248 KB	Output isn't correct
14	Correct	0 ms	32248 KB	Output is correct
15	Incorrect	3 ms	32248 KB	Output isn't correct
16	Correct	0 ms	32248 KB	Output is correct
17	Correct	3 ms	32248 KB	Output is correct
18	Correct	0 ms	32248 KB	Output is correct
19	Correct	0 ms	32248 KB	Output is correct
20	Correct	6 ms	32248 KB	Output is correct
21	Correct	0 ms	32248 KB	Output is correct
22	Incorrect	0 ms	32248 KB	Output isn't correct
23	Incorrect	0 ms	32248 KB	Output isn't correct
24	Incorrect	0 ms	32248 KB	Output isn't correct
25	Incorrect	0 ms	32248 KB	Output isn't correct
26	Correct	0 ms	32248 KB	Output is correct
27	Incorrect	0 ms	32248 KB	Output isn't correct
28	Correct	0 ms	32248 KB	Output is correct
29	Correct	3 ms	32248 KB	Output is correct
30	Incorrect	0 ms	32248 KB	Output isn't correct
31	Correct	3 ms	32248 KB	Output is correct
32	Correct	0 ms	32248 KB	Output is correct
33	Incorrect	0 ms	32248 KB	Output isn't correct
34	Incorrect	3 ms	32248 KB	Output isn't correct
35	Correct	0 ms	32248 KB	Output is correct
36	Correct	3 ms	32248 KB	Output is correct
37	Correct	6 ms	32248 KB	Output is correct
38	Incorrect	6 ms	32248 KB	Output isn't correct
39	Incorrect	0 ms	32248 KB	Output isn't correct
40	Correct	0 ms	32248 KB	Output is correct
41	Correct	0 ms	32248 KB	Output is correct
42	Incorrect	0 ms	32248 KB	Output isn't correct
43	Correct	3 ms	32248 KB	Output is correct
44	Correct	0 ms	32248 KB	Output is correct
45	Incorrect	3 ms	32248 KB	Output isn't correct
46	Incorrect	0 ms	32248 KB	Output isn't correct
47	Incorrect	0 ms	32248 KB	Output isn't correct
48	Incorrect	0 ms	32248 KB	Output isn't correct
49	Incorrect	0 ms	32248 KB	Output isn't correct
50	Incorrect	0 ms	32248 KB	Output isn't correct
51	Correct	0 ms	32248 KB	Output is correct
52	Correct	3 ms	32248 KB	Output is correct
53	Correct	3 ms	32248 KB	Output is correct
54	Incorrect	6 ms	32248 KB	Output isn't correct
55	Correct	16 ms	32524 KB	Output is correct
56	Incorrect	19 ms	32524 KB	Output isn't correct
57	Incorrect	16 ms	32524 KB	Output isn't correct
58	Correct	19 ms	32524 KB	Output is correct
59	Correct	19 ms	32524 KB	Output is correct
60	Incorrect	13 ms	32524 KB	Output isn't correct
61	Correct	13 ms	32524 KB	Output is correct
62	Correct	9 ms	32392 KB	Output is correct
63	Incorrect	3 ms	32248 KB	Output isn't correct
64	Correct	19 ms	32524 KB	Output is correct
65	Correct	13 ms	32524 KB	Output is correct
66	Incorrect	16 ms	32524 KB	Output isn't correct
67	Incorrect	9 ms	32392 KB	Output isn't correct
68	Incorrect	6 ms	32392 KB	Output isn't correct
69	Correct	16 ms	32524 KB	Output is correct

Subtask #5
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	32248 KB	Output is correct
2	Incorrect	0 ms	32248 KB	Output isn't correct
3	Correct	0 ms	32248 KB	Output is correct
4	Incorrect	0 ms	32248 KB	Output isn't correct
5	Incorrect	0 ms	32248 KB	Output isn't correct
6	Incorrect	0 ms	32248 KB	Output isn't correct
7	Incorrect	0 ms	32248 KB	Output isn't correct
8	Incorrect	3 ms	32248 KB	Output isn't correct
9	Correct	0 ms	32248 KB	Output is correct
10	Correct	0 ms	32248 KB	Output is correct
11	Correct	0 ms	32248 KB	Output is correct
12	Correct	0 ms	32248 KB	Output is correct
13	Incorrect	3 ms	32248 KB	Output isn't correct
14	Correct	0 ms	32248 KB	Output is correct
15	Incorrect	3 ms	32248 KB	Output isn't correct
16	Correct	0 ms	32248 KB	Output is correct
17	Correct	3 ms	32248 KB	Output is correct
18	Correct	0 ms	32248 KB	Output is correct
19	Correct	0 ms	32248 KB	Output is correct
20	Correct	6 ms	32248 KB	Output is correct
21	Correct	0 ms	32248 KB	Output is correct
22	Incorrect	0 ms	32248 KB	Output isn't correct
23	Incorrect	0 ms	32248 KB	Output isn't correct
24	Incorrect	0 ms	32248 KB	Output isn't correct
25	Incorrect	0 ms	32248 KB	Output isn't correct
26	Correct	0 ms	32248 KB	Output is correct
27	Incorrect	0 ms	32248 KB	Output isn't correct
28	Correct	0 ms	32248 KB	Output is correct
29	Correct	3 ms	32248 KB	Output is correct
30	Incorrect	0 ms	32248 KB	Output isn't correct
31	Correct	3 ms	32248 KB	Output is correct
32	Correct	0 ms	32248 KB	Output is correct
33	Incorrect	0 ms	32248 KB	Output isn't correct
34	Incorrect	3 ms	32248 KB	Output isn't correct
35	Correct	0 ms	32248 KB	Output is correct
36	Correct	3 ms	32248 KB	Output is correct
37	Correct	6 ms	32248 KB	Output is correct
38	Incorrect	6 ms	32248 KB	Output isn't correct
39	Incorrect	0 ms	32248 KB	Output isn't correct
40	Correct	0 ms	32248 KB	Output is correct
41	Correct	0 ms	32248 KB	Output is correct
42	Incorrect	0 ms	32248 KB	Output isn't correct
43	Correct	3 ms	32248 KB	Output is correct
44	Correct	0 ms	32248 KB	Output is correct
45	Incorrect	3 ms	32248 KB	Output isn't correct
46	Incorrect	0 ms	32248 KB	Output isn't correct
47	Incorrect	0 ms	32248 KB	Output isn't correct
48	Incorrect	0 ms	32248 KB	Output isn't correct
49	Incorrect	0 ms	32248 KB	Output isn't correct
50	Incorrect	0 ms	32248 KB	Output isn't correct
51	Correct	0 ms	32248 KB	Output is correct
52	Correct	3 ms	32248 KB	Output is correct
53	Correct	3 ms	32248 KB	Output is correct
54	Incorrect	6 ms	32248 KB	Output isn't correct
55	Correct	16 ms	32524 KB	Output is correct
56	Incorrect	19 ms	32524 KB	Output isn't correct
57	Incorrect	16 ms	32524 KB	Output isn't correct
58	Correct	19 ms	32524 KB	Output is correct
59	Correct	19 ms	32524 KB	Output is correct
60	Incorrect	13 ms	32524 KB	Output isn't correct
61	Correct	13 ms	32524 KB	Output is correct
62	Correct	9 ms	32392 KB	Output is correct
63	Incorrect	3 ms	32248 KB	Output isn't correct
64	Correct	19 ms	32524 KB	Output is correct
65	Correct	13 ms	32524 KB	Output is correct
66	Incorrect	16 ms	32524 KB	Output isn't correct
67	Incorrect	9 ms	32392 KB	Output isn't correct
68	Incorrect	6 ms	32392 KB	Output isn't correct
69	Correct	16 ms	32524 KB	Output is correct
70	Incorrect	23 ms	32524 KB	Output isn't correct
71	Incorrect	386 ms	35408 KB	Output isn't correct
72	Correct	319 ms	35408 KB	Output is correct
73	Incorrect	376 ms	35408 KB	Output isn't correct
74	Correct	346 ms	35408 KB	Output is correct
75	Correct	389 ms	35408 KB	Output is correct
76	Correct	369 ms	35408 KB	Output is correct
77	Incorrect	149 ms	33872 KB	Output isn't correct
78	Correct	363 ms	35408 KB	Output is correct
79	Incorrect	369 ms	35408 KB	Output isn't correct
80	Incorrect	363 ms	35408 KB	Output isn't correct
81	Correct	73 ms	33104 KB	Output is correct
82	Correct	246 ms	35408 KB	Output is correct
83	Incorrect	369 ms	35408 KB	Output isn't correct
84	Correct	363 ms	35408 KB	Output is correct
85	Incorrect	383 ms	35408 KB	Output isn't correct
86	Incorrect	373 ms	35408 KB	Output isn't correct
87	Correct	369 ms	35408 KB	Output is correct
88	Incorrect	59 ms	32720 KB	Output isn't correct
89	Incorrect	209 ms	33872 KB	Output isn't correct
90	Correct	173 ms	33872 KB	Output is correct
91	Correct	13 ms	32524 KB	Output is correct
92	Correct	156 ms	33872 KB	Output is correct

Submission #20463

Compilation message

Subtask #1 0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 0 / 23.0

Subtask #4 0 / 26.0

Subtask #5 0 / 28.0

Subtask #1
0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
0 / 23.0

Subtask #4
0 / 26.0

Subtask #5
0 / 28.0