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;
typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 300010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N,D,S,A[maxn];
int disc[maxn], undisc[maxn];
int F[maxn],G[maxn];
struct node{
int s,e,m,val=0,num=0;
node *l,*r;
node(int ss,int ee){
s = ss; e = ee; m = (s + e) / 2;
if (s != e){
l = new node(s,m); r = new node(m+1,e);
}
}
void upd(int p,int v){
if (s == e){
val += undisc[s] * v; num += v;
}else{
if (p > m) r->upd(p, v);
else l->upd(p,v);
val = l->val + r->val;
num = l->num + r->num;
}
}
int qry(int v){
if (s == e) return (v > 0) * val;
if (r->num < v) return r->val + l->qry(v-r->num);
else return r->qry(v);
}
void clear(){
val = num = 0;
if (s != e){
l->clear(); r->clear();
}
}
}*root;
int M;
int Fval[maxn], Gval[maxn];
void dnc(int l,int r,int vl,int vr){
// root is at vl-1
if (l > r) return;
int m = (l + r) / 2;
F[m] = vl; int cur = -1;
FOR(i,vl,vr){ // s to i
root->upd(disc[i], 1);
int val = root->qry(m - (i - S));
if (val > cur){
cur = val; F[m] = i;
}
}
//cout << m << ' ' << cur << '\n';
Fval[m] = cur;
FOR(i,F[m],vr) root->upd(disc[i], -1);
dnc(m+1,r,F[m],vr);
FOR(i,vl,F[m]-1) root->upd(disc[i], -1);
dnc(l,m-1,vl,F[m]);
}
void backdnc(int l,int r,int vl,int vr){
// root is at vr+1
if (l > r) return;
int m = (l + r) / 2;
G[m] = vr; int cur = -1;
DEC(i,vr,vl){ // i to s
root->upd(disc[i], 1);
int val = root->qry(m - (S-1 - i));
if (val > cur){
cur = val; G[m] = i;
}
}
//cout << m << ' ' << Gval[m] << ' ' << cur << '\n';
Gval[m] = cur;
FOR(i,vl,G[m]) root->upd(disc[i], -1);
backdnc(m+1,r,vl,G[m]);
FOR(i,G[m]+1,vr) root->upd(disc[i], -1);
backdnc(l,m-1,G[m],vr);
}
int B[maxn];
int solve(){
vi v2;
FOR(i,0,S) v2.pb(B[i]);
FOR(i,S+1,N-1){v2.pb(0); v2.pb(B[i]);} // model return moves
M = v2.size();
FOR(i,0,M-1) A[i] = v2[i];
vpi v;
FOR(i,0,M-1) v.pb(pi(A[i], i));
sort(all(v));
FOR(i,0,M-1){
disc[v[i].s] = i; undisc[i] = v[i].f;
}
root->clear();
dnc(0, D, S, M-1);
root->clear();
backdnc(0,D,0,S-1);
int ans = max(Fval[D], Gval[D-1]);
FOR(i,0,D){ // number of days spent going right
if (D - i - 1 >= 0){
ans = max(ans, Gval[D - i -1] + Fval[i]);
}
}
return ans;
}
ll findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
N = n; D = d; S = start;
root = new node(0,2*N-1);
FOR(i,0,N-1) B[i] = attraction[i];
int ans = solve();
reverse(B, B+N);
S = N - 1 - S;
ans = max(ans, solve());
return ans;
}
# | 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... |