# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
684112 | vovamr | Mountain Trek Route (IZhO12_route) | C++17 | 317 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
#define int long long
inline void solve() {
int n, k;
cin >> n >> k;
auto get_len = [&n](int l, int r) {
if (l <= r) return r - l + 1;
else return n - (l - r) + 1;
};
ve<int> a(n);
for (auto &i : a) cin >> i;
if (*max_element(all(a)) == *min_element(all(a))) {
cout << 0;
return;
}
set<array<int,3>> segs;
{
int ptr = n;
while (ptr - 1 >= 0 && a[ptr - 1] == a[0]) --ptr;
int L = (ptr == n ? 0 : ptr);
for (int i = 0; i < n; ) {
if (i >= ptr) break;
int j = i;
while (j < n && a[j] == a[i]) ++j;
segs.insert(array<int,3>{j - 1, i == 0 ? L : i, a[i]});
i = j;
}
}
set<array<int,3>>::iterator nxt, prev;
set<array<int,2>> active;
for (auto it = segs.begin(); it != segs.end(); ++it) {
if (it == --segs.end()) nxt = segs.begin();
else nxt = it, ++nxt;
if (it == segs.begin()) prev = --segs.end();
else prev = it, --prev;
int vp = (*prev)[2];
int vn = (*nxt)[2];
int vc = (*it)[2];
if (vp > vc && vn > vc) {
auto &[r, l, x] = *it;
active.insert( array<int,2>{ get_len(l, r), l } );
}
}
ve<array<int,3>> nw;
ll ans = 0;
while (k && sz(active)) {
auto [len, l] = *active.begin();
int r = (l + len - 1 + n) % n;
active.erase(active.begin());
auto it = segs.lower_bound(array<int,3>{r, l, -iinf});
if (it == --segs.end()) nxt = segs.begin();
else nxt = it, ++nxt;
if (it == segs.begin()) prev = --segs.end();
else prev = it, --prev;
auto [rp, lp, vp] = *prev;
auto [rn, ln, vn] = *nxt;
int vc = (*it)[2];
int can = min(k / len, min(vp, vn) - vc);
assert(min(vp, vn) > vc);
if (!can) break;
k -= can * len; ans += 2 * can;
segs.erase(array<int,3>{r, l, vc});
segs.erase(array<int,3>{rn, ln, vn});
if (make_tuple(rp, lp, vp) != make_tuple(rn, ln, vn)) segs.erase(array<int,3>{rp, lp, vp});
else {
break;
}
vc += can;
nw.clear();
nw.shrink_to_fit();
if (vp != vc) {
nw.pb({rp, lp, vp});
if (vc != vn) {
nw.pb({r, l, vc});
nw.pb({rn, ln, vn});
}
else {
nw.pb({rn, l, vc});
}
}
else if (vp == vc && vc != vn) {
nw.pb({r, lp, vc});
nw.pb({rn, ln, vn});
}
else {
nw.pb({rn, l, vc});
}
for (auto &[r, l, x] : nw) {
segs.insert(array<int,3>{r, l, x});
}
for (auto &[r, l, x] : nw) {
auto it = segs.find({r, l, x});
if (it == --segs.end()) nxt = segs.begin();
else nxt = it, ++nxt;
if (it == segs.begin()) prev = --segs.end();
else prev = it, --prev;
int vp = (*prev)[2];
int vn = (*nxt)[2];
int vc = (*it)[2];
if (vp > vc && vn > vc) {
active.insert( array<int,2>{ get_len(l, r), l } );
}
}
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |