이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "Lgrader.cpp"
#define endl '\n'
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
struct node
{
int cnt;
int64_t sum;
node *l, *r;
node() { l = r = nullptr; sum = cnt = 0; }
};
using pnode = node*;
pnode merge(pnode l, pnode r)
{
pnode ret = new node();
ret->l = l;
ret->r = r;
ret->cnt = l->cnt + r->cnt;
ret->sum = l->sum + r->sum;
return ret;
}
vector<int> cmpr;
int get(int x) { return lower_bound(cmpr.begin(), cmpr.end(), x) - cmpr.begin(); }
int SZ;
pnode build(int l, int r)
{
if(l == r)
return new node();
int mid = (l + r) >> 1;
return merge(build(l, mid), build(mid + 1, r));
}
pnode add(int x, int l, int r, pnode t)
{
if(x < l || x > r)
return t;
if(l == r)
{
pnode it = new node();
it->cnt = t->cnt + 1;
it->sum = t->sum + cmpr[SZ - x];
return it;
}
int mid = (l + r) >> 1;
return merge(add(x, l, mid, t->l), add(x, mid + 1, r, t->r));
}
int64_t get(int k, int l, int r, pnode A, pnode B)
{
if(l == r)
{
int c = min(k, A->cnt - B->cnt);
int64_t ret = c * 1ll * cmpr[SZ - l];
return ret;
}
int mid = (l + r) >> 1;
if(A->l->cnt - B->l->cnt < k) return A->l->sum - B->l->sum + get(k - (A->l->cnt - B->l->cnt), mid + 1, r, A->r, B->r);
else return get(k, l, mid, A->l, B->l);
}
int n, a[MAXN], start, d;
pnode t[MAXN], emp, last;
int64_t eval(int l, int r)
{
int cnt = (r - l) * 2 - max(abs(start - l), abs(start - r));
cnt = max(0, d - cnt);
if(l == 0) return get(cnt, 0, SZ, t[r], emp);
else return get(cnt, 0, SZ, t[r], t[l - 1]);
}
int opt[MAXN];
int64_t value[MAXN];
void rec(int l, int r, int opt_l, int opt_r)
{
if(l > r)
return;
int mid = (l + r) >> 1;
opt[mid] = l;
value[mid] = -(int64_t)1e18;
for(int i = start; i < n; i++)
if(chkmax(value[i], eval(mid, i)))
opt[mid] = i;
rec(l, mid - 1, opt_l, opt[mid]);
rec(mid + 1, r, opt[mid], opt_r);
}
long long findMaxAttraction(int n, int start, int d, int attraction[])
{
::n = n;
::start = start;
::d = d;
for(int i = 0; i < n; i++)
a[i] = attraction[i];
for(int i = 0; i < n; i++) cmpr.push_back(a[i]);
sort(cmpr.begin(), cmpr.end());
cmpr.erase(unique(cmpr.begin(), cmpr.end()), cmpr.end());
SZ = cmpr.size() - 1;
last = emp = build(0, SZ);
for(int i = 0; i < n; i++)
last = t[i] = add(SZ - get(a[i]), 0, SZ, last);
/*
for(int i = 0; i <= start; i++)
for(int j = start; j < n; j++)
cout << i << " " << j << " : " << eval(i, j) << endl;
*/
rec(0, start, start, n - 1);
int64_t answer = 0;
for(int i = 0; i < n; i++)
chkmax(answer, value[i]);
return answer;
}
컴파일 시 표준 에러 (stderr) 메시지
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |