Submission #206912

#	Time	Username	Problem	Language	Result	Execution time	Memory
206912		tduong0806	Holiday (IOI14_holiday)	C++14	24 / 100	221 ms	65540 KiB

holiday

#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 (stderr)

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;
                                               ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53