• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

trungore10 May 23rd, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. using namespace std;
3.
4. typedef pair<int, int> ii;
5.
6. const int N = 1e5 + 4, oo = 1e9 + 7;
7. int n, k, a[N];
8.
9. struct Interval_Tree {
10.     int minNode[4*N], maxNode[4*N];
11.
12.     void update(int i, int l, int r, int x, int y, int val) {
13.         if (l > y || x > r) return;
14.         if (x <= l && r <= y) {
15.             minNode[i] = maxNode[i] = val;
16.             return;
17.         }
18.         int mid = (l + r) / 2;
19.         update(2*i, l, mid, x, y, val);
20.         update(2*i+1, mid+1, r, x, y, val);
21.         minNode[i] = min(minNode[2*i], minNode[2*i+1]);
22.         maxNode[i] = max(maxNode[2*i], maxNode[2*i+1]);
23.     }
24.
25.     ii get(int i, int l, int r, int x, int y) {
26.         if (l > y || x > r) return ii(oo, -oo);
27.         if (x <= l && r <= y) return ii(minNode[i], maxNode[i]);
28.         int mid = (l + r) / 2;
29.         ii tmp1 = get(2*i, l, mid, x, y), tmp2 = get(2*i+1, mid+1, r, x, y);
30.         return ii( min(tmp1.first, tmp2.first), max(tmp1.second, tmp2.second) );
31.     }
32. } IT;
33.
34. vector<ii> ans;
35.
36. bool check(int mid) {
37.     ans.clear();
38.     for (int l = 1; l <= n-mid+1; ++l) {
39.         int r = l + mid - 1;
40.         ii tmp = IT.get(1, 1, n, l, r);
41.         if (tmp.second - tmp.first <= k) ans.push_back(ii(l, r));
42.     }
43.     if (ans.size()) return true;
44.     return false;
45. }
46.
47. void sol() {
48.     for (int i = 1; i <= n; ++i) IT.update(1, 1, n, i, i, a[i]);
49.
50.     int l = 1, r = n, res = -1;
51.     while (l <= r) {
52.         int mid = (l + r) / 2;
53.         if (check(mid)) { res = mid; l = mid + 1; }
54.         else r = mid - 1;
55.     }
56.
57.     check(res);
58.
59.     cout << res << " " << ans.size() << '\n';
60.     for (ii seg : ans) cout << seg.first << " " << seg.second << '\n';
61. }
62.
63. int main() {
64.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
65.     if (fopen("input.txt", "r")) {
66.         freopen("input.txt", "r", stdin);
67.         freopen("output.txt", "w", stdout);
68.     }
69.
70.     cin >> n >> k;
71.     for (int i = 1; i <= n; ++i) cin >> a[i];
72.
73.     sol();
74.
75.     return 0;
76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top