SHARE
TWEET

Untitled

trungore10 May 23rd, 2019 80 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. OK, I Understand
 
Top