Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> ii;
- const int N = 1e5 + 4, oo = 1e9 + 7;
- int n, k, a[N];
- struct Interval_Tree {
- int minNode[4*N], maxNode[4*N];
- void update(int i, int l, int r, int x, int y, int val) {
- if (l > y || x > r) return;
- if (x <= l && r <= y) {
- minNode[i] = maxNode[i] = val;
- return;
- }
- int mid = (l + r) / 2;
- update(2*i, l, mid, x, y, val);
- update(2*i+1, mid+1, r, x, y, val);
- minNode[i] = min(minNode[2*i], minNode[2*i+1]);
- maxNode[i] = max(maxNode[2*i], maxNode[2*i+1]);
- }
- ii get(int i, int l, int r, int x, int y) {
- if (l > y || x > r) return ii(oo, -oo);
- if (x <= l && r <= y) return ii(minNode[i], maxNode[i]);
- int mid = (l + r) / 2;
- ii tmp1 = get(2*i, l, mid, x, y), tmp2 = get(2*i+1, mid+1, r, x, y);
- return ii( min(tmp1.first, tmp2.first), max(tmp1.second, tmp2.second) );
- }
- } IT;
- vector<ii> ans;
- bool check(int mid) {
- ans.clear();
- for (int l = 1; l <= n-mid+1; ++l) {
- int r = l + mid - 1;
- ii tmp = IT.get(1, 1, n, l, r);
- if (tmp.second - tmp.first <= k) ans.push_back(ii(l, r));
- }
- if (ans.size()) return true;
- return false;
- }
- void sol() {
- for (int i = 1; i <= n; ++i) IT.update(1, 1, n, i, i, a[i]);
- int l = 1, r = n, res = -1;
- while (l <= r) {
- int mid = (l + r) / 2;
- if (check(mid)) { res = mid; l = mid + 1; }
- else r = mid - 1;
- }
- check(res);
- cout << res << " " << ans.size() << '\n';
- for (ii seg : ans) cout << seg.first << " " << seg.second << '\n';
- }
- int main() {
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- if (fopen("input.txt", "r")) {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- }
- cin >> n >> k;
- for (int i = 1; i <= n; ++i) cin >> a[i];
- sol();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement