SHARE
TWEET

Untitled

a guest Oct 21st, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <bitset>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <math.h>
  9. #include <iomanip>
  10. typedef long long ll;
  11. using namespace std;
  12. #define all(v) v.begin(), v.end()
  13. #define pb push_back
  14. #define ff first
  15. #define ss second
  16. #define fori(n) for (int i = 0; i < n; i++)
  17. #define forj(n) for (int j = 0; j < n; j++)
  18.  
  19. #pragma GCC optimize("unroll-loops")
  20. #pragma GCC optimize("Ofast")
  21. #pragma GCC optimize("no-stack-protector")
  22. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  23. #pragma GCC optimize("fast-math")
  24. #pragma GCC optimize "-O3"
  25.  
  26.  
  27. int n, k;
  28. vector < int > a;
  29. vector < int > pref;
  30. int main() {
  31.     cin >> n >> k;
  32.     a.resize(n);
  33.     pref.resize(n);
  34.     fori(n) cin >> a[i];
  35.     fori(n) {
  36.         if (i) pref[i] = pref[i - 1];
  37.         pref[i] += a[i];
  38.     }
  39.     pair < int, int > ans;
  40.     int dist = 1e9 + 228;
  41.     for (int i = 0; i < n; i++) {
  42.         /// i - первый элемент, который мы взяли
  43.         int need = k;
  44.         if (i) need += pref[i - 1];
  45.         /// нам надо взять такой отрезок[i;y], что
  46.         /// pref[y] - pref[i - 1] = k
  47.         /// ищем такой минимальный y, что pref[y] = pref[i - 1] + k
  48.         int l = i, r = n - 1;
  49.         while (l != r) {
  50.             //cout << l << " " << r << "\n";
  51.             int m = (l + r) / 2;
  52.             if (pref[m] == need) {r = m; continue;}
  53.             if (pref[m + 1] > need) r = m;
  54.             else l = m + 1;
  55.         }
  56.         if (pref[l] != need) continue;
  57.         if (dist > l - i) {
  58.             dist = l - i;
  59.             ans = {i, l};
  60.         }
  61.     }
  62.     if (dist == 1e9 + 228) { /// если у нас не нашелся такой отрезок, и dist остался таким же
  63.         cout << -1;
  64.     } else {
  65.         cout << ans.ff + 1 << " " << ans.ss + 1 << "\n";
  66.     }
  67. }
  68. /*
  69. */
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