Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bitset>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <math.h>
- #include <iomanip>
- typedef long long ll;
- using namespace std;
- #define all(v) v.begin(), v.end()
- #define pb push_back
- #define ff first
- #define ss second
- #define fori(n) for (int i = 0; i < n; i++)
- #define forj(n) for (int j = 0; j < n; j++)
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")
- #pragma GCC optimize "-O3"
- int n, k;
- vector < int > a;
- vector < int > pref;
- int main() {
- cin >> n >> k;
- a.resize(n);
- pref.resize(n);
- fori(n) cin >> a[i];
- fori(n) {
- if (i) pref[i] = pref[i - 1];
- pref[i] += a[i];
- }
- pair < int, int > ans;
- int dist = 1e9 + 228;
- for (int i = 0; i < n; i++) {
- /// i - первый элемент, который мы взяли
- int need = k;
- if (i) need += pref[i - 1];
- /// нам надо взять такой отрезок[i;y], что
- /// pref[y] - pref[i - 1] = k
- /// ищем такой минимальный y, что pref[y] = pref[i - 1] + k
- int l = i, r = n - 1;
- while (l != r) {
- //cout << l << " " << r << "\n";
- int m = (l + r) / 2;
- if (pref[m] == need) {r = m; continue;}
- if (pref[m + 1] > need) r = m;
- else l = m + 1;
- }
- if (pref[l] != need) continue;
- if (dist > l - i) {
- dist = l - i;
- ans = {i, l};
- }
- }
- if (dist == 1e9 + 228) { /// если у нас не нашелся такой отрезок, и dist остался таким же
- cout << -1;
- } else {
- cout << ans.ff + 1 << " " << ans.ss + 1 << "\n";
- }
- }
- /*
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement