선분 n개가 주어진다.
이 중 하나를 뺐을 때 나머지 모든 선분의 교집합의 길이의 최대값을 출력하는 문제.
sqrt decompostion을 썼는데 알고보니 최대값, 최대값 다음값, 최소값, 최소값 다음값 네개만 가지고 있으면 되는 문제였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <iostream> #include <algorithm> #include <math.h> using namespace std; int n; pair<int, int> arr[300001]; int min_v[600], max_v[600]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; int siz = sqrt(n); fill(min_v, min_v + 599, 2e9); for (int i = 0; i < n; ++i) { cin >> arr[i].first >> arr[i].second; min_v[i / siz] = min(min_v[i / siz], arr[i].second); max_v[i / siz] = max(max_v[i / siz], arr[i].first); } int ans = 0; for (int i = 0; i < n; ++i) { // a[i]를 제외한다면 int a, b, minv, maxv; // 0 ~ i-1, i+1~n-1 minv = 2e9; maxv = 0; // l a = 0; b = i - 1; while (a%siz != 0 && a <= b) { minv = min(minv, arr[a].second); maxv = max(maxv, arr[a++].first); } while ((b + 1) % siz != 0 && a <= b) { minv = min(minv, arr[b].second); maxv = max(maxv, arr[b--].first); } while (a <= b) { minv = min(minv, min_v[a/siz]); maxv = max(maxv, max_v[a/siz]); a += siz; } // r a = i + 1; b = n - 1; while (a%siz != 0 && a <= b) { minv = min(minv, arr[a].second); maxv = max(maxv, arr[a++].first); } while ((b + 1) % siz != 0 && a <= b) { minv = min(minv, arr[b].second); maxv = max(maxv, arr[b--].first); } while (a <= b) { minv = min(minv, min_v[a / siz]); maxv = max(maxv, max_v[a / siz]); a += siz; } ans = max(ans, minv - maxv); } cout << ans; return 0; } | cs |
'codeforces > #506 div3' 카테고리의 다른 글
F. Multicolored Markers (0) | 2018.08.29 |
---|---|
D. Concatenated Multiples (0) | 2018.08.29 |
B. Creating the Contest (0) | 2018.08.29 |
A. Many Equal Substrings (0) | 2018.08.29 |