#include <bits/stdc++.h> using namespace std; map<long long, int> mapka; long long bk = 0; int bv = 0; void put(long long k, int v) { auto it = mapka.lower_bound(k-bk); if (it != mapka.end()) { if (it->second < v-bv) { return; } } vector<long long> torem; while (it != mapka.begin()) { it--; if (it->second > v-bv) { torem.push_back(it->first); } } for (long long r : torem) { mapka.erase(r); } mapka[k-bk] = v-bv; } int get(long long k) { return mapka[k-bk] + bv; } void inckey(long long diff) { bk += diff; } void incval(int diff) { bv += diff; } pair<bool, pair<long long, int>> lower(long long k) { auto it = mapka.lower_bound(k-bk); if (it == mapka.end()) { return {false, {-1,-1}}; } return {true, {it->first+bk, it->second+bv}}; } void solve() { int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } put(0, 0); long long offset = 0; for (int i = 0; i < n; i++) { inckey(v[i]); incval(1); auto lp = lower(0); if (lp.first) { auto p = lp.second; put(0, p.second-1); } } auto lp = lower(0); if (lp.first) { auto p = lp.second; cout << p.second << "\n"; } else { cout << "-1\n"; } } int main() { ios_base::sync_with_stdio(false); cout.precision(15); cout << fixed; cin.tie(0); int T = 1; //cin >> T; for (int tst = 0; tst < T; tst++) { solve(); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <bits/stdc++.h> using namespace std; map<long long, int> mapka; long long bk = 0; int bv = 0; void put(long long k, int v) { auto it = mapka.lower_bound(k-bk); if (it != mapka.end()) { if (it->second < v-bv) { return; } } vector<long long> torem; while (it != mapka.begin()) { it--; if (it->second > v-bv) { torem.push_back(it->first); } } for (long long r : torem) { mapka.erase(r); } mapka[k-bk] = v-bv; } int get(long long k) { return mapka[k-bk] + bv; } void inckey(long long diff) { bk += diff; } void incval(int diff) { bv += diff; } pair<bool, pair<long long, int>> lower(long long k) { auto it = mapka.lower_bound(k-bk); if (it == mapka.end()) { return {false, {-1,-1}}; } return {true, {it->first+bk, it->second+bv}}; } void solve() { int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } put(0, 0); long long offset = 0; for (int i = 0; i < n; i++) { inckey(v[i]); incval(1); auto lp = lower(0); if (lp.first) { auto p = lp.second; put(0, p.second-1); } } auto lp = lower(0); if (lp.first) { auto p = lp.second; cout << p.second << "\n"; } else { cout << "-1\n"; } } int main() { ios_base::sync_with_stdio(false); cout.precision(15); cout << fixed; cin.tie(0); int T = 1; //cin >> T; for (int tst = 0; tst < T; tst++) { solve(); } return 0; } |