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 "grader.cpp"
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 1e5 + 5;
struct SegmentTree
{
int cnt;
long long sum;
SegmentTree *L, *R;
void build(int l, int r)
{
cnt = sum = 0;
if(l==r) return;
L = new SegmentTree();
R = new SegmentTree();
L->build(l, (l+r)/2);
R->build((l+r)/2+1, r);
}
void update(int q, int cntChange, int sumChange, int l, int r, SegmentTree *other)
{
cnt = other->cnt;
sum = other->sum;
if(l==r)
{
cnt += cntChange;
sum += sumChange;
return;
}
if(l<=q && q<=(l+r)/2)
{
L = new SegmentTree();
L->update(q, cntChange, sumChange, l, (l+r)/2, other->L);
}
else
{
L = other->L;
}
if((l+r)/2+1<=q && q<=r)
{
R = new SegmentTree();
R->update(q, cntChange, sumChange, (l+r)/2+1, r, other->R);
}
else
{
R = other->R;
}
cnt = L->cnt + R->cnt;
sum = L->sum + R->sum;
}
long long getTop(int getCnt, int l, int r)
{
if(sum==0) return 0;
if(getCnt==0) return 0;
if(getCnt>=cnt) return sum;
if(l==r) return min(getCnt, cnt)*(sum/cnt);
if(R->cnt<=getCnt) return R->sum + L->getTop(getCnt-R->cnt, l, (l+r)/2);
return R->getTop(getCnt, (l+r)/2+1, r);
}
};
SegmentTree *base;
map <int, int> numCode;
SegmentTree *T[MAXN];
void init(int *a, int n, int start)
{
set <int> s;
for(int i = 0;i<n;i++)
s.insert(a[i]);
int ind = 0;
for(int x: s)
{
numCode[x] = ind;
ind++;
}
base = new SegmentTree();
base->build(0, numCode.size()-1);
//T[start] = new SegmentTree();
//T[start]->update(numCode[ a[start] ], 1, a[start], 0, numCode.size()-1, base);
T[start] = base;
for(int i = start-1;i>=0;i--)
{
T[i] = new SegmentTree();
T[i]->update(numCode[ a[i] ], 1, a[i], 0, numCode.size()-1, T[i+1]);
}
for(int i = start+1;i<n;i++)
{
T[i] = new SegmentTree();
T[i]->update(numCode[ a[i] ], 1, a[i], 0, numCode.size()-1, T[i-1]);
}
}
long long evalSegment(int start, int finish, int d)
{
d -= abs(start-finish);
return T[finish]->getTop(d, 0, numCode.size()-1);
}
long long solve1(int n, int start, int d)
{
long long answer = 0;
int lastLOpt = start, lastROpt = n - 1;
function <long long(int, int, int, pair <int, int>, pair <int, int>)> solve = [&]
(int d, int lD, int rD, pair <int, int> lOptBorders, pair <int, int> rOptBorders)
{
if(lD>rD) return 0LL;
long long answer = 0;
int dLeft = (lD+rD)/2, dRight = d - dLeft;
int lOpt = start;
long long currL = 0;
for(int l = lOptBorders.second;l>=lOptBorders.first;l--)
{
if((start-l)*2>dLeft) break;
long long val = evalSegment(start, l, dLeft-(start-l));
if(currL<val)
{
currL = val;
lOpt = l;
}
}
int rOpt = start;
long long currR = 0;
for(int r = rOptBorders.first;r<=rOptBorders.second;r++)
{
if(r-start>dRight) break;
long long val = evalSegment(start, r, dRight);
if(currR<=val)
{
currR = val;
rOpt = r;
}
}
answer = max(answer, currL+currR);
answer = max(solve(d, lD, dLeft-1, make_pair(lOpt, lOptBorders.second), make_pair(rOpt, rOptBorders.second)), answer);
answer = max(solve(d, dLeft+1, rD, make_pair(lOptBorders.first, lOpt), make_pair(rOptBorders.first, rOpt)), answer);
return answer;
};
return solve(d, 0, d, make_pair(0, start-1), make_pair(start+1, n-1));
}
long long solve2(int n, int start, int d)
{
long long answer = 0;
int lastLOpt = start, lastROpt = n - 1;
function <long long(int, int, int, pair <int, int>, pair <int, int>)> solve = [&]
(int d, int lD, int rD, pair <int, int> lOptBorders, pair <int, int> rOptBorders)
{
if(lD>rD) return 0LL;
long long answer = 0;
int dLeft = (lD+rD)/2, dRight = d - dLeft;
int lOpt = start;
long long currL = 0;
for(int l = lOptBorders.second;l>=lOptBorders.first;l--)
{
if(start-l>dLeft) break;
long long val = evalSegment(start, l, dLeft);
if(currL<val)
{
currL = val;
lOpt = l;
}
}
int rOpt = start;
long long currR = 0;
for(int r = rOptBorders.first;r<=rOptBorders.second;r++)
{
if((r-start)*2>dRight) break;
long long val = evalSegment(start, r, dRight-(r-start));
if(currR<=val)
{
currR = val;
rOpt = r;
}
}
answer = max(answer, currL+currR);
answer = max(solve(d, lD, dLeft-1, make_pair(lOpt, lOptBorders.second), make_pair(rOpt, rOptBorders.second)), answer);
answer = max(solve(d, dLeft+1, rD, make_pair(lOptBorders.first, lOpt), make_pair(rOptBorders.first, rOpt)), answer);
return answer;
};
return solve(d, 0, d, make_pair(0, start-1), make_pair(start+1, n-1));
}
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
init(attraction, n, start);
long long answer = 0;
answer = max(answer, solve1(n, start, d));
answer = max(answer, solve1(n, start, d-1) + attraction[start]);
answer = max(answer, solve2(n, start, d));
answer = max(answer, solve2(n, start, d-1) + attraction[start]);
return answer;
}
Compilation message (stderr)
holiday.cpp: In function 'long long int solve1(int, int, int)':
holiday.cpp:129:15: warning: unused variable 'answer' [-Wunused-variable]
129 | long long answer = 0;
| ^~~~~~
holiday.cpp:130:9: warning: unused variable 'lastLOpt' [-Wunused-variable]
130 | int lastLOpt = start, lastROpt = n - 1;
| ^~~~~~~~
holiday.cpp:130:27: warning: unused variable 'lastROpt' [-Wunused-variable]
130 | int lastLOpt = start, lastROpt = n - 1;
| ^~~~~~~~
holiday.cpp: In function 'long long int solve2(int, int, int)':
holiday.cpp:180:15: warning: unused variable 'answer' [-Wunused-variable]
180 | long long answer = 0;
| ^~~~~~
holiday.cpp:181:9: warning: unused variable 'lastLOpt' [-Wunused-variable]
181 | int lastLOpt = start, lastROpt = n - 1;
| ^~~~~~~~
holiday.cpp:181:27: warning: unused variable 'lastROpt' [-Wunused-variable]
181 | int lastLOpt = start, lastROpt = n - 1;
| ^~~~~~~~
# | 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... |