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 "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define all(v) v.begin(), v.end()
const int maxn = 7e3+100;
//#define int ll
#define pii pair <int, int>
ll inf = 1e18;
ll n, m, ukl, ukr, d, ts[4*maxn], tc[4*maxn], pos[maxn], a[maxn], res = -inf;
pair <ll, int> b[maxn];
void upd(int v, int tl, int tr, int pos, ll val)
{
// if(v == 1) cout << "UPDATE " << pos << " " << val << endl;
if(pos < tl || tr < pos) return;
if(tl == tr)
{
ts[v] += val;
if(ts[v] > 0) tc[v]++;
else tc[v]--;
return;
}
upd(v * 2, tl, (tl + tr) / 2, pos, val);
upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val);
ts[v] = ts[v * 2] + ts[v * 2 + 1];
tc[v] = tc[v * 2] + tc[v * 2 + 1];
}
ll get(int v, int tl, int tr, int k)
{
if(tl == tr)
{
return ts[v];
}
if(tc[v * 2 + 1] >= k) return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, k);
else return get(v * 2, tl, (tl + tr) / 2, k - tc[v * 2 + 1]) + ts[v * 2 + 1];
}
void print(int v, int tl, int tr)
{
if(tl == tr)
{
cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl;
return;
}
print(v * 2, tl, (tl + tr) / 2);
cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl;
print(v * 2 + 1, (tl + tr) / 2 + 1, tr);
}
void solve(int l, int r, int optl = m, int optr = n)
{
if(l > r) return;
int mid = (l + r) / 2;
while(ukl > mid)
{
ukl--;
upd(1, 1, n, pos[ukl], a[ukl]);
}
while(ukl < mid)
{
upd(1, 1, n, pos[ukl], -a[ukl]);
ukl++;
}
ll ans = -inf;
int opt;
forn(optl, i, optr)
{
while(ukr < i)
{
ukr++;
upd(1, 1, n, pos[ukr], a[ukr]);
}
while(ukr > i)
{
upd(1, 1, n, pos[ukr], -a[ukr]);
ukr--;
}
//m-mid
//i-m
// cout << "FOR " << mid << " " << i << " " << d-(i-mid+min(i-m, m-mid)) << " " << get(1, 1, n, d-(i-mid+min(i-m, m-mid))) << " " << ukl << " " << ukr << endl;
// print(1, 1, n);
ll temp = get(1, 1, n, d-(i-mid+min(i-m, m-mid)));
res = max(res, temp);
if(temp > ans)
{
ans = temp;
opt = i;
}
}
// cout << mid << " " << opt << endl;
solve(l, mid-1, optl, opt);
solve(mid+1, r, opt, optr);
}
long long int findMaxAttraction(int N, int start, int D, int attraction[])
{
n = N;
d = D;
forn(1, i, n)
{
b[i].f = attraction[i-1];
b[i].s = i;
a[i] = b[i].f;
}
sort(b + 1, b + 1 + n);
forn(1, i, n)
{
pos[b[i].s] = i;
}
start++;
m = start;
ukr = start;
ukl = start;
upd(1, 1, n, pos[start], a[start]);
solve(1, start);
return res;
}
Compilation message (stderr)
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:102:7: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | solve(l, mid-1, optl, opt);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |