# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
71002 | 2018-08-24T01:57:54 Z | 김세빈(#2203) | Global Warming (CEOI18_glo) | C++11 | 2000 ms | 64584 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){ S[T[p].l].erase(c); 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, j, 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++){ for(j=i+1; j<=n; j++){ if(A[i] - x < A[j]) ans = max(ans, L[i] + R[j]); } } /* 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 | 56 ms | 62072 KB | Output is correct |
2 | Correct | 57 ms | 62184 KB | Output is correct |
3 | Correct | 56 ms | 62260 KB | Output is correct |
4 | Correct | 57 ms | 62260 KB | Output is correct |
5 | Correct | 54 ms | 62260 KB | Output is correct |
6 | Correct | 46 ms | 62260 KB | Output is correct |
7 | Correct | 56 ms | 62260 KB | Output is correct |
8 | Correct | 55 ms | 62260 KB | Output is correct |
9 | Correct | 62 ms | 62260 KB | Output is correct |
10 | Correct | 50 ms | 62272 KB | Output is correct |
11 | Correct | 48 ms | 62272 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 62072 KB | Output is correct |
2 | Correct | 57 ms | 62184 KB | Output is correct |
3 | Correct | 56 ms | 62260 KB | Output is correct |
4 | Correct | 57 ms | 62260 KB | Output is correct |
5 | Correct | 54 ms | 62260 KB | Output is correct |
6 | Correct | 46 ms | 62260 KB | Output is correct |
7 | Correct | 56 ms | 62260 KB | Output is correct |
8 | Correct | 55 ms | 62260 KB | Output is correct |
9 | Correct | 62 ms | 62260 KB | Output is correct |
10 | Correct | 50 ms | 62272 KB | Output is correct |
11 | Correct | 48 ms | 62272 KB | Output is correct |
12 | Correct | 49 ms | 62272 KB | Output is correct |
13 | Correct | 48 ms | 62272 KB | Output is correct |
14 | Correct | 47 ms | 62272 KB | Output is correct |
15 | Correct | 48 ms | 62272 KB | Output is correct |
16 | Correct | 51 ms | 62272 KB | Output is correct |
17 | Correct | 47 ms | 62444 KB | Output is correct |
18 | Correct | 47 ms | 62444 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 62072 KB | Output is correct |
2 | Correct | 57 ms | 62184 KB | Output is correct |
3 | Correct | 56 ms | 62260 KB | Output is correct |
4 | Correct | 57 ms | 62260 KB | Output is correct |
5 | Correct | 54 ms | 62260 KB | Output is correct |
6 | Correct | 46 ms | 62260 KB | Output is correct |
7 | Correct | 56 ms | 62260 KB | Output is correct |
8 | Correct | 55 ms | 62260 KB | Output is correct |
9 | Correct | 62 ms | 62260 KB | Output is correct |
10 | Correct | 50 ms | 62272 KB | Output is correct |
11 | Correct | 48 ms | 62272 KB | Output is correct |
12 | Correct | 49 ms | 62272 KB | Output is correct |
13 | Correct | 48 ms | 62272 KB | Output is correct |
14 | Correct | 47 ms | 62272 KB | Output is correct |
15 | Correct | 48 ms | 62272 KB | Output is correct |
16 | Correct | 51 ms | 62272 KB | Output is correct |
17 | Correct | 47 ms | 62444 KB | Output is correct |
18 | Correct | 47 ms | 62444 KB | Output is correct |
19 | Correct | 50 ms | 62444 KB | Output is correct |
20 | Correct | 56 ms | 62444 KB | Output is correct |
21 | Correct | 59 ms | 62444 KB | Output is correct |
22 | Correct | 50 ms | 62444 KB | Output is correct |
23 | Correct | 60 ms | 62444 KB | Output is correct |
24 | Correct | 51 ms | 62444 KB | Output is correct |
25 | Correct | 48 ms | 62444 KB | Output is correct |
26 | Correct | 50 ms | 62444 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2067 ms | 64584 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2043 ms | 64584 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2052 ms | 64584 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 62072 KB | Output is correct |
2 | Correct | 57 ms | 62184 KB | Output is correct |
3 | Correct | 56 ms | 62260 KB | Output is correct |
4 | Correct | 57 ms | 62260 KB | Output is correct |
5 | Correct | 54 ms | 62260 KB | Output is correct |
6 | Correct | 46 ms | 62260 KB | Output is correct |
7 | Correct | 56 ms | 62260 KB | Output is correct |
8 | Correct | 55 ms | 62260 KB | Output is correct |
9 | Correct | 62 ms | 62260 KB | Output is correct |
10 | Correct | 50 ms | 62272 KB | Output is correct |
11 | Correct | 48 ms | 62272 KB | Output is correct |
12 | Correct | 49 ms | 62272 KB | Output is correct |
13 | Correct | 48 ms | 62272 KB | Output is correct |
14 | Correct | 47 ms | 62272 KB | Output is correct |
15 | Correct | 48 ms | 62272 KB | Output is correct |
16 | Correct | 51 ms | 62272 KB | Output is correct |
17 | Correct | 47 ms | 62444 KB | Output is correct |
18 | Correct | 47 ms | 62444 KB | Output is correct |
19 | Correct | 50 ms | 62444 KB | Output is correct |
20 | Correct | 56 ms | 62444 KB | Output is correct |
21 | Correct | 59 ms | 62444 KB | Output is correct |
22 | Correct | 50 ms | 62444 KB | Output is correct |
23 | Correct | 60 ms | 62444 KB | Output is correct |
24 | Correct | 51 ms | 62444 KB | Output is correct |
25 | Correct | 48 ms | 62444 KB | Output is correct |
26 | Correct | 50 ms | 62444 KB | Output is correct |
27 | Execution timed out | 2067 ms | 64584 KB | Time limit exceeded |
28 | Halted | 0 ms | 0 KB | - |