# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
70999 | 2018-08-24T01:54:53 Z | 김세빈(#2203) | Global Warming (CEOI18_glo) | C++11 | 654 ms | 74468 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, 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 | 49 ms | 61944 KB | Output is correct |
2 | Incorrect | 58 ms | 62180 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 61944 KB | Output is correct |
2 | Incorrect | 58 ms | 62180 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 61944 KB | Output is correct |
2 | Incorrect | 58 ms | 62180 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 654 ms | 73912 KB | Output is correct |
2 | Correct | 600 ms | 73916 KB | Output is correct |
3 | Correct | 579 ms | 73916 KB | Output is correct |
4 | Correct | 632 ms | 74148 KB | Output is correct |
5 | Correct | 302 ms | 74456 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 160 ms | 74456 KB | Output is correct |
2 | Correct | 170 ms | 74456 KB | Output is correct |
3 | Correct | 158 ms | 74456 KB | Output is correct |
4 | Incorrect | 105 ms | 74456 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 243 ms | 74456 KB | Output is correct |
2 | Correct | 241 ms | 74456 KB | Output is correct |
3 | Correct | 496 ms | 74456 KB | Output is correct |
4 | Correct | 317 ms | 74468 KB | Output is correct |
5 | Correct | 141 ms | 74468 KB | Output is correct |
6 | Correct | 198 ms | 74468 KB | Output is correct |
7 | Correct | 215 ms | 74468 KB | Output is correct |
8 | Correct | 210 ms | 74468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 61944 KB | Output is correct |
2 | Incorrect | 58 ms | 62180 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |