| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 871301 | TAhmed33 | Weirdtree (RMI21_weirdtree) | C++17 | 0 ms | 0 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 <weirdtree.h>
using namespace std;
typedef long long ll;
int n;
ll arr[1001];
void initialise (int N, int q, int h[]) {
n = N;
for (int i = 1; i <= n; i++) {
arr[i] = h[i];
}
}
void cut (int l, int r, int k) {
vector <pair <ll, ll>> dd;
ll sum = 0;
for (int i = l; i <= r; i++) {
if (arr[i] < 0) assert(0);
dd.push_back({arr[i], i});
sum += arr[i];
}
if (sum <= k) {
for (int i = l; i <= r; i++) arr[i] = 0;
return;
}
sort(dd.begin(), dd.end(), [] (pair <ll, ll> &a, pair <ll, ll> &b) {
return a.first == b.first ? a.second < b.second : a.first > b.first;
});
dd.push_back({0, (ll)1e9});
for (int i = 1; i < (int)dd.size(); i++) {
if (dd[i].first == dd[i - 1].first) continue;
ll t = (dd[i - 1].first - dd[i].first) * i;
if (t <= k) {
k -= t;
continue;
}
ll y = k / i;
for (int j = 0; j < i; j++) arr[dd[j].second] = y;
k -= y;
for (int j = 0; j < k; j++) arr[dd[j].second]--;
return;
}
}
ll inspect (int l, int r) {
ll sum = 0;
for (int i = l; i <= r; i++) {
if (arr[i] < 0) assert(0);
sum += arr[i];
}
return sum;
}