Submission #20462

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20462	2017-02-11T23:37:11 Z	책상다리황새두렁넘기(#60, khsoo01)	Can polan into space? (OJUZ11_space)	C++11	0 / 100	376 ms	40232 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], ord[200005], cc;
bool chk[200005];
pair<ll,ll> dt[200005], ans;
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;
		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(1, i-1, b[i]);
		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+1;i<=n;i++) ord[i] = i;
	for(int i=ans.Y;i;i=dt[i].Y) {ord[i] = ++cc; chk[i] = true;}
	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[j] = ++cc;
		for(int j=i-1;j>=tmp.Y;j--) ord[j] = ++cc;
	}
	while(--i) ord[i] = ++cc;
	for(int i=1;i<=n;i++) printf("%lld ",ord[i]);
}

Compilation message

space.cpp: In function 'int main()':
space.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
space.cpp:60: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	3 ms	34004 KB	Output is correct
2	Incorrect	0 ms	34004 KB	Output isn't correct
3	Correct	3 ms	34004 KB	Output is correct
4	Incorrect	0 ms	34004 KB	Output isn't correct
5	Incorrect	0 ms	34004 KB	Output isn't correct
6	Incorrect	0 ms	34004 KB	Output isn't correct
7	Incorrect	3 ms	34004 KB	Output isn't correct
8	Incorrect	3 ms	34004 KB	Output isn't correct
9	Correct	0 ms	34004 KB	Output is correct
10	Incorrect	3 ms	34004 KB	Output isn't correct
11	Incorrect	3 ms	34004 KB	Output isn't correct
12	Incorrect	0 ms	34004 KB	Output isn't correct
13	Incorrect	0 ms	34004 KB	Output isn't correct
14	Correct	3 ms	34004 KB	Output is correct
15	Incorrect	3 ms	34004 KB	Output isn't correct
16	Correct	0 ms	34004 KB	Output is correct
17	Incorrect	0 ms	34004 KB	Output isn't correct
18	Incorrect	0 ms	34004 KB	Output isn't correct
19	Incorrect	0 ms	34004 KB	Output isn't correct
20	Incorrect	0 ms	34004 KB	Output isn't correct
21	Incorrect	0 ms	34004 KB	Output isn't correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	34004 KB	Output is correct
2	Incorrect	0 ms	34004 KB	Output isn't correct
3	Correct	3 ms	34004 KB	Output is correct
4	Incorrect	0 ms	34004 KB	Output isn't correct
5	Incorrect	0 ms	34004 KB	Output isn't correct
6	Incorrect	0 ms	34004 KB	Output isn't correct
7	Incorrect	3 ms	34004 KB	Output isn't correct
8	Incorrect	3 ms	34004 KB	Output isn't correct
9	Correct	0 ms	34004 KB	Output is correct
10	Incorrect	3 ms	34004 KB	Output isn't correct
11	Incorrect	3 ms	34004 KB	Output isn't correct
12	Incorrect	0 ms	34004 KB	Output isn't correct
13	Incorrect	0 ms	34004 KB	Output isn't correct
14	Correct	3 ms	34004 KB	Output is correct
15	Incorrect	3 ms	34004 KB	Output isn't correct
16	Correct	0 ms	34004 KB	Output is correct
17	Incorrect	0 ms	34004 KB	Output isn't correct
18	Incorrect	0 ms	34004 KB	Output isn't correct
19	Incorrect	0 ms	34004 KB	Output isn't correct
20	Incorrect	0 ms	34004 KB	Output isn't correct
21	Incorrect	0 ms	34004 KB	Output isn't correct
22	Incorrect	3 ms	34004 KB	Output isn't correct
23	Incorrect	0 ms	34004 KB	Output isn't correct
24	Incorrect	6 ms	34004 KB	Output isn't correct
25	Incorrect	0 ms	34004 KB	Output isn't correct
26	Incorrect	0 ms	34004 KB	Output isn't correct
27	Incorrect	0 ms	34004 KB	Output isn't correct
28	Correct	3 ms	34004 KB	Output is correct
29	Incorrect	0 ms	34004 KB	Output isn't correct
30	Incorrect	0 ms	34004 KB	Output isn't correct
31	Correct	0 ms	34004 KB	Output is correct
32	Incorrect	0 ms	34004 KB	Output isn't correct
33	Incorrect	3 ms	34004 KB	Output isn't correct
34	Incorrect	0 ms	34004 KB	Output isn't correct
35	Incorrect	0 ms	34004 KB	Output isn't correct
36	Incorrect	0 ms	34004 KB	Output isn't correct
37	Incorrect	0 ms	34004 KB	Output isn't correct
38	Incorrect	0 ms	34004 KB	Output isn't correct
39	Incorrect	3 ms	34004 KB	Output isn't correct
40	Correct	3 ms	34004 KB	Output is correct
41	Incorrect	0 ms	34004 KB	Output isn't correct
42	Incorrect	0 ms	34004 KB	Output isn't correct
43	Incorrect	0 ms	34004 KB	Output isn't correct
44	Correct	3 ms	34004 KB	Output is correct
45	Incorrect	3 ms	34004 KB	Output isn't correct
46	Incorrect	0 ms	34004 KB	Output isn't correct
47	Incorrect	0 ms	34004 KB	Output isn't correct
48	Incorrect	0 ms	34004 KB	Output isn't correct
49	Incorrect	3 ms	34004 KB	Output isn't correct
50	Incorrect	0 ms	34004 KB	Output isn't correct
51	Incorrect	0 ms	34004 KB	Output isn't correct
52	Incorrect	0 ms	34004 KB	Output isn't correct
53	Incorrect	0 ms	34004 KB	Output isn't correct
54	Incorrect	0 ms	34004 KB	Output isn't correct
55	Incorrect	13 ms	34004 KB	Output isn't correct
56	Incorrect	13 ms	34004 KB	Output isn't correct
57	Incorrect	13 ms	34004 KB	Output isn't correct
58	Incorrect	19 ms	34004 KB	Output isn't correct
59	Incorrect	19 ms	34004 KB	Output isn't correct
60	Incorrect	13 ms	34004 KB	Output isn't correct
61	Correct	9 ms	34472 KB	Output is correct
62	Incorrect	9 ms	34004 KB	Output isn't correct
63	Incorrect	6 ms	34004 KB	Output isn't correct
64	Incorrect	13 ms	34004 KB	Output isn't correct
65	Correct	13 ms	34004 KB	Output is correct
66	Incorrect	13 ms	34004 KB	Output isn't correct
67	Incorrect	6 ms	34004 KB	Output isn't correct
68	Incorrect	6 ms	34004 KB	Output isn't correct
69	Incorrect	13 ms	34004 KB	Output isn't correct
70	Incorrect	16 ms	34004 KB	Output isn't correct
71	Incorrect	363 ms	34004 KB	Output isn't correct
72	Correct	286 ms	40232 KB	Output is correct
73	Incorrect	356 ms	34004 KB	Output isn't correct
74	Correct	353 ms	34004 KB	Output is correct
75	Incorrect	376 ms	34004 KB	Output isn't correct
76	Incorrect	366 ms	34004 KB	Output isn't correct
77	Incorrect	143 ms	34004 KB	Output isn't correct
78	Incorrect	356 ms	34004 KB	Output isn't correct
79	Incorrect	359 ms	34004 KB	Output isn't correct
80	Incorrect	366 ms	34004 KB	Output isn't correct
81	Incorrect	66 ms	34004 KB	Output isn't correct
82	Incorrect	249 ms	34004 KB	Output isn't correct
83	Incorrect	359 ms	34004 KB	Output isn't correct
84	Incorrect	343 ms	34004 KB	Output isn't correct
85	Incorrect	336 ms	34004 KB	Output isn't correct
86	Incorrect	366 ms	34004 KB	Output isn't correct
87	Incorrect	339 ms	34004 KB	Output isn't correct
88	Incorrect	49 ms	34004 KB	Output isn't correct
89	Incorrect	213 ms	34004 KB	Output isn't correct
90	Incorrect	153 ms	34004 KB	Output isn't correct
91	Incorrect	13 ms	34004 KB	Output isn't correct
92	Incorrect	149 ms	34004 KB	Output isn't correct

Submission #20462

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