#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int hmt() {int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';if(n) x=-x;return x;}
#define in hmt()
#define ins ({string x;char c=getchar();for(;c==' '||c=='\n';c=getchar());for(;c!=' '&&c!='\n';c=getchar()) x+=c;x;})
#define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forb(i,BS) for(int i=BS._Find_first();i< BS.size();i = BS._Find_next(i))
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
const int N=310000;
int n,st,d,t[N],a[N],b[N];
ll l[N],r[N],L[N],R[N];
vector<pii> e;
pii sv[N];
int v(int i) {return lower_bound(all(e),make_pair(a[i],i))-e.begin()+1;}
struct node
{
int pass=0,c=0;
ll t=0;
node *left,*right;
void make()
{
if(pass) return;pass=1;
left=new node;
right=new node;
}
} *rt[N];
void upd(node *s,node *p,int l,int r,int u,int x)
{
if(l==r)
{
s->t=p->t+x;
s->c=p->c+1;
return;
}
s->make();p->make();
int mid=(l+r)/2;
if(mid>=u)
{
s->right=p->right;
upd(s->left,p->left,l,mid,u,x);
}
else
{
s->left=p->left;
upd(s->right,p->right,mid+1,r,u,x);
}
s->t=s->left->t+s->right->t;
s->c=s->left->c+s->right->c;
}
ll Find(node *s,int l,int r,int k)
{
if( l == r) return s->t;
s -> make();int mid=(l+r)/2;
if(s -> right ->c >= k) return Find( s -> right,mid+1,r,k);
return s->right->t+Find(s -> left,l,mid,k - s -> right -> c);
}
void upd(int i,int x)
{
for(;i<N;i+=i&-i) t[i]=max(t[i],x);
}
int get(int i)
{
int g=0;
for(;i;i-=i&-i) g=max(g,t[i]);
return g;
}
void buildl(ll *l,int x)
{
reset(t,0);
forinc(i,0,n+1) rt[i]=new node;
upd(rt[st],rt[st+1],1,n,v(st),a[st]);
l[1]=a[st];
upd(1,N-st);
fordec(i,st-1,1)
{
upd(rt[i],rt[i+1],1,n,v(i),a[i]);
int le=(x+1)*(st-i)+1,ri=(x+2)*(st-i),o;
while(le<=ri)
{
int m=(le+ri)/2;
int j=N-get(m);
if(j==N||Find(rt[i],1,n,m-(st-i)*(x+1))>=Find(rt[j],1,n,m-(st-j)*(x+1))) o=m,ri=m-1;
else le=m+1;
}
upd(o,N-i);
}
forinc(i,1,d)
{
int j=N-get(i);
l[i]=l[i-1];
if(j!=N) l[i]=max(l[i],Find(rt[j],1,n,i-(st-j)*(x+1)));
}
}
void buildr(ll *r,int x)
{
reset(t,0);
forinc(i,0,n+1) rt[i]=new node;
forinc(i,st+1,n)
{
upd(rt[i],rt[i-1],1,n,v(i),a[i]);
int le=(x+1)*(i-st)+1,ri=(x+2)*(i-st),o;
while(le<=ri)
{
int m=(le+ri)/2;
int j=get(m);
if(!j||Find(rt[i],1,n,m-(i-st)*(x+1))>=Find(rt[j],1,n,m-(j-st)*(x+1))) o=m,ri=m-1;
else le=m+1;
}
upd(o,i);
}
forinc(i,1,d)
{
int j=get(i);
r[i]=r[i-1];
if(j) r[i]=max(r[i],Find(rt[j],1,n,i-(j-st)*(x+1)));
}
}
ll findMaxAttraction(int nn,int stt,int dd,int b[])
{
n=nn,st=stt+1,d=dd;
forinc(i,1,n) a[i]=b[i-1];
forinc(i,1,n) e.pb({a[i],i});
sort(all(e));
buildl(l,0);
buildl(L,1);
buildr(r,0);
buildr(R,1);
ll ans=0;
forinc(i,0,d) ans=max({ans,l[i]+R[d-i],L[i]+r[d-i]});
return ans;
}
/*main()
{
freopen("HOLIDAY.inp","r",stdin);
freopen("HOLIDAY.out","w",stdout);
n=in,st=in+1,d=in;
forinc(i,1,n) a[i]=in,e.pb({a[i],i});
sort(all(e));
buildl(l,0);
buildl(L,1);
buildr(r,0);
buildr(R,1);
ll ans=0;
forinc(i,0,d) ans=max({ans,l[i]+R[d-i],L[i]+r[d-i]});
cout<<ans<<"\n";
}
*/
Compilation message
holiday.cpp: In member function 'void node::make()':
holiday.cpp:35:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(pass) return;pass=1;
^~
holiday.cpp:35:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(pass) return;pass=1;
^~~~
holiday.cpp: In function 'void buildl(ll*, int)':
holiday.cpp:72:15: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(;i<N;i+=i&-i) t[i]=max(t[i],x);
~^~~~~~
holiday.cpp:90:47: note: 'o' was declared here
int le=(x+1)*(st-i)+1,ri=(x+2)*(st-i),o;
^
holiday.cpp: In function 'void buildr(ll*, int)':
holiday.cpp:72:15: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(;i<N;i+=i&-i) t[i]=max(t[i],x);
~^~~~~~
holiday.cpp:114:47: note: 'o' was declared here
int le=(x+1)*(i-st)+1,ri=(x+2)*(i-st),o;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
9604 KB |
Output is correct |
| 2 |
Correct |
27 ms |
9592 KB |
Output is correct |
| 3 |
Correct |
28 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
26 ms |
9336 KB |
Output is correct |
| 5 |
Correct |
25 ms |
8440 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3832 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3960 KB |
Output is correct |
| 8 |
Correct |
11 ms |
3960 KB |
Output is correct |
| 9 |
Correct |
11 ms |
3960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
221 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
