# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
71003 | 2018-08-24T01:59:07 Z | 김세빈(#2203) | Global Warming (CEOI18_glo) | C++11 | 667 ms | 74516 KB |
#include <bits/stdc++.h> using namespace std; struct node{ int l, r, v; node() : l(0), r(0), v(0) {} }; node T[4040404]; multiset <int> S[303030]; int A[202020], L[202020], R[202020], D[202020]; int n, x, ans, tp, sp; void insert(int p, int s, int e, int v, int c) { if(s == e){ if(!T[p].l) T[p].l = ++sp; S[T[p].l].insert(c); T[p].v = *prev(S[T[p].l].end()); } else{ if(v <= (s + e >> 1)){ if(!T[p].l) T[p].l = ++tp; insert(T[p].l, s, (s + e >> 1), v, c); } else{ if(!T[p].r) T[p].r = ++tp; insert(T[p].r, (s + e >> 1) + 1, e, v, c); } T[p].v = max(T[T[p].l].v, T[T[p].r].v); } } void erase(int p, int s, int e, int v, int c) { if(s == e){ auto it = S[T[p].l].lower_bound(c); S[T[p].l].erase(it); if(S[T[p].l].empty()) T[p].v = 0; else T[p].v = *prev(S[T[p].l].end()); } else{ if(v <= (s + e >> 1)){ erase(T[p].l, s, (s + e >> 1), v, c); } else{ erase(T[p].r, (s + e >> 1) + 1, e, v, c); } T[p].v = max(T[T[p].l].v, T[T[p].r].v); } } int get_max(int p, int s, int e, int l, int r) { if(!p || e < l || r < s) return 0; else if(l <= s && e <= r) return T[p].v; else return max(get_max(T[p].l, s, (s + e >> 1), l, r), get_max(T[p].r, (s + e >> 1) + 1, e, l, r)); } int main() { int i, g, k; scanf("%d%d", &n, &x); for(i=1; i<=n; i++){ scanf("%d", A + i); } g = 1; for(i=1; i<=n; i++){ k = lower_bound(D, D + g, A[i]) - D; if(k == g) g ++; L[i] = k; D[k] = A[i]; } g = 1; for(i=n; i>=1; i--){ k = lower_bound(D, D + g, 1e9 - A[i] + 1) - D; if(k == g) g ++; R[i] = k; D[k] = 1e9 - A[i] + 1; } tp = 1; for(i=1; i<=n; i++){ insert(1, 1, 1e9, A[i], R[i]); } for(i=1; i<=n; i++){ erase(1, 1, 1e9, A[i], R[i]); ans = max(ans, L[i] + get_max(1, 1, 1e9, A[i] - x + 1, 1e9)); } printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 62072 KB | Output is correct |
2 | Correct | 52 ms | 62304 KB | Output is correct |
3 | Correct | 48 ms | 62304 KB | Output is correct |
4 | Correct | 50 ms | 62304 KB | Output is correct |
5 | Correct | 49 ms | 62304 KB | Output is correct |
6 | Correct | 52 ms | 62304 KB | Output is correct |
7 | Correct | 52 ms | 62304 KB | Output is correct |
8 | Correct | 54 ms | 62304 KB | Output is correct |
9 | Correct | 56 ms | 62304 KB | Output is correct |
10 | Correct | 50 ms | 62304 KB | Output is correct |
11 | Correct | 55 ms | 62304 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 62072 KB | Output is correct |
2 | Correct | 52 ms | 62304 KB | Output is correct |
3 | Correct | 48 ms | 62304 KB | Output is correct |
4 | Correct | 50 ms | 62304 KB | Output is correct |
5 | Correct | 49 ms | 62304 KB | Output is correct |
6 | Correct | 52 ms | 62304 KB | Output is correct |
7 | Correct | 52 ms | 62304 KB | Output is correct |
8 | Correct | 54 ms | 62304 KB | Output is correct |
9 | Correct | 56 ms | 62304 KB | Output is correct |
10 | Correct | 50 ms | 62304 KB | Output is correct |
11 | Correct | 55 ms | 62304 KB | Output is correct |
12 | Correct | 64 ms | 62304 KB | Output is correct |
13 | Correct | 56 ms | 62304 KB | Output is correct |
14 | Correct | 58 ms | 62304 KB | Output is correct |
15 | Correct | 50 ms | 62304 KB | Output is correct |
16 | Correct | 51 ms | 62304 KB | Output is correct |
17 | Correct | 57 ms | 62304 KB | Output is correct |
18 | Correct | 50 ms | 62304 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 62072 KB | Output is correct |
2 | Correct | 52 ms | 62304 KB | Output is correct |
3 | Correct | 48 ms | 62304 KB | Output is correct |
4 | Correct | 50 ms | 62304 KB | Output is correct |
5 | Correct | 49 ms | 62304 KB | Output is correct |
6 | Correct | 52 ms | 62304 KB | Output is correct |
7 | Correct | 52 ms | 62304 KB | Output is correct |
8 | Correct | 54 ms | 62304 KB | Output is correct |
9 | Correct | 56 ms | 62304 KB | Output is correct |
10 | Correct | 50 ms | 62304 KB | Output is correct |
11 | Correct | 55 ms | 62304 KB | Output is correct |
12 | Correct | 64 ms | 62304 KB | Output is correct |
13 | Correct | 56 ms | 62304 KB | Output is correct |
14 | Correct | 58 ms | 62304 KB | Output is correct |
15 | Correct | 50 ms | 62304 KB | Output is correct |
16 | Correct | 51 ms | 62304 KB | Output is correct |
17 | Correct | 57 ms | 62304 KB | Output is correct |
18 | Correct | 50 ms | 62304 KB | Output is correct |
19 | Correct | 49 ms | 62332 KB | Output is correct |
20 | Correct | 52 ms | 62332 KB | Output is correct |
21 | Correct | 50 ms | 62332 KB | Output is correct |
22 | Correct | 51 ms | 62336 KB | Output is correct |
23 | Correct | 52 ms | 62336 KB | Output is correct |
24 | Correct | 52 ms | 62356 KB | Output is correct |
25 | Correct | 48 ms | 62436 KB | Output is correct |
26 | Correct | 48 ms | 62436 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 617 ms | 74024 KB | Output is correct |
2 | Correct | 650 ms | 74236 KB | Output is correct |
3 | Correct | 667 ms | 74236 KB | Output is correct |
4 | Correct | 642 ms | 74236 KB | Output is correct |
5 | Correct | 337 ms | 74492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 174 ms | 74492 KB | Output is correct |
2 | Correct | 180 ms | 74492 KB | Output is correct |
3 | Correct | 177 ms | 74492 KB | Output is correct |
4 | Correct | 109 ms | 74492 KB | Output is correct |
5 | Correct | 58 ms | 74492 KB | Output is correct |
6 | Correct | 162 ms | 74492 KB | Output is correct |
7 | Correct | 144 ms | 74492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 234 ms | 74492 KB | Output is correct |
2 | Correct | 239 ms | 74492 KB | Output is correct |
3 | Correct | 517 ms | 74492 KB | Output is correct |
4 | Correct | 243 ms | 74516 KB | Output is correct |
5 | Correct | 120 ms | 74516 KB | Output is correct |
6 | Correct | 188 ms | 74516 KB | Output is correct |
7 | Correct | 196 ms | 74516 KB | Output is correct |
8 | Correct | 176 ms | 74516 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 62072 KB | Output is correct |
2 | Correct | 52 ms | 62304 KB | Output is correct |
3 | Correct | 48 ms | 62304 KB | Output is correct |
4 | Correct | 50 ms | 62304 KB | Output is correct |
5 | Correct | 49 ms | 62304 KB | Output is correct |
6 | Correct | 52 ms | 62304 KB | Output is correct |
7 | Correct | 52 ms | 62304 KB | Output is correct |
8 | Correct | 54 ms | 62304 KB | Output is correct |
9 | Correct | 56 ms | 62304 KB | Output is correct |
10 | Correct | 50 ms | 62304 KB | Output is correct |
11 | Correct | 55 ms | 62304 KB | Output is correct |
12 | Correct | 64 ms | 62304 KB | Output is correct |
13 | Correct | 56 ms | 62304 KB | Output is correct |
14 | Correct | 58 ms | 62304 KB | Output is correct |
15 | Correct | 50 ms | 62304 KB | Output is correct |
16 | Correct | 51 ms | 62304 KB | Output is correct |
17 | Correct | 57 ms | 62304 KB | Output is correct |
18 | Correct | 50 ms | 62304 KB | Output is correct |
19 | Correct | 49 ms | 62332 KB | Output is correct |
20 | Correct | 52 ms | 62332 KB | Output is correct |
21 | Correct | 50 ms | 62332 KB | Output is correct |
22 | Correct | 51 ms | 62336 KB | Output is correct |
23 | Correct | 52 ms | 62336 KB | Output is correct |
24 | Correct | 52 ms | 62356 KB | Output is correct |
25 | Correct | 48 ms | 62436 KB | Output is correct |
26 | Correct | 48 ms | 62436 KB | Output is correct |
27 | Correct | 617 ms | 74024 KB | Output is correct |
28 | Correct | 650 ms | 74236 KB | Output is correct |
29 | Correct | 667 ms | 74236 KB | Output is correct |
30 | Correct | 642 ms | 74236 KB | Output is correct |
31 | Correct | 337 ms | 74492 KB | Output is correct |
32 | Correct | 174 ms | 74492 KB | Output is correct |
33 | Correct | 180 ms | 74492 KB | Output is correct |
34 | Correct | 177 ms | 74492 KB | Output is correct |
35 | Correct | 109 ms | 74492 KB | Output is correct |
36 | Correct | 58 ms | 74492 KB | Output is correct |
37 | Correct | 162 ms | 74492 KB | Output is correct |
38 | Correct | 144 ms | 74492 KB | Output is correct |
39 | Correct | 234 ms | 74492 KB | Output is correct |
40 | Correct | 239 ms | 74492 KB | Output is correct |
41 | Correct | 517 ms | 74492 KB | Output is correct |
42 | Correct | 243 ms | 74516 KB | Output is correct |
43 | Correct | 120 ms | 74516 KB | Output is correct |
44 | Correct | 188 ms | 74516 KB | Output is correct |
45 | Correct | 196 ms | 74516 KB | Output is correct |
46 | Correct | 176 ms | 74516 KB | Output is correct |
47 | Correct | 277 ms | 74516 KB | Output is correct |
48 | Correct | 273 ms | 74516 KB | Output is correct |
49 | Correct | 554 ms | 74516 KB | Output is correct |
50 | Correct | 265 ms | 74516 KB | Output is correct |
51 | Correct | 189 ms | 74516 KB | Output is correct |
52 | Correct | 251 ms | 74516 KB | Output is correct |
53 | Correct | 199 ms | 74516 KB | Output is correct |
54 | Correct | 207 ms | 74516 KB | Output is correct |
55 | Correct | 389 ms | 74516 KB | Output is correct |