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>
#define ll long long
using namespace std;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e5 + 10;
vector <int> save[N];
struct fen{
vector <ll> f;
int N;
void ass(int n) {
N = n;
f.assign(N + 1, 0);
}
void upd(int i, ll x) {
for (; i; i -= i & (-i))
f[i] += x;
}
ll get(int i) {
ll s = 0;
for (; i <= N; i += N)
s += f[i];
return s;
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int n = N;
int c = C;
int r = R;
for (int i = 0; i < c; i++) {
S[i]++;
E[i] += 2;
}
set <int> pos;
for (int i = 1; i <= n; i++) {
if (K[i - 1] > r) {
pos.insert(i);
}
}
pos.insert(n + 1);
for (int i = 0; i < c; i++) {
auto it = pos.lower_bound(S[i]);
E[i] = min(E[i], *it);
save[S[i]].pb(E[i]);
}
fen f1, f2;
f1.ass(n + 10);
f2.ass(n + 10);
priority_queue <int, vector <int>, greater <int>> pq;
ll ans = 0, p = 0;
for (ll i = 1; i <= n; i++) {
for (auto x : save[i]) {
pq.push(x);
f1.upd(x, 1);
f2.upd(x, x);
}
while (sz(pq) && pq.top() <= i) {
int t = pq.top();
f1.upd(t, -1);
f2.upd(t, -t);
pq.pop();
}
ll v = f2.get(i) - f1.get(i) * i;
if (ans < v) {
ans = v;
p = i - 1;
}
}
return p;
}
// 2 2
// 1 2
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |