Submission #1066103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066103		noyancanturk	Holiday (IOI14_holiday)	C++17	100 / 100	1114 ms	6768 KiB

holiday

#include"holiday.h"

#include<bits/stdc++.h>
using namespace std;

using lint = long long int;

using pii=pair<lint,int>;

const int lim=1e5+100;

int n,s,d,a[lim];

lint ans=0;

struct treap{
    struct Node{
        int val;
        lint sum;
        int pri,cnt;
        Node*l,*r;
        Node(int val):val(val),sum(val),pri(rand()),cnt(1),l(0),r(0){}
    };
    using pnode=Node*;
    inline int getcnt(const pnode&p){
        if(p)return p->cnt;
        return 0;
    }
    inline lint getsum(const pnode&p){
        if(p)return p->sum;
        return 0;
    }
    inline void updcnt(pnode p){
        if(p){
            p->cnt=1+getcnt(p->l)+getcnt(p->r);
            p->sum=p->val+getsum(p->l)+getsum(p->r);
        }
    }
    inline void split(pnode p,pnode&l,pnode&r,int val){
        if(!p){
            l=r=0;
            return;
        }
        if(val<=p->val){
            split(p->l,l,p->l,val);
            r=p;
        }else{
            split(p->r,p->r,r,val);
            l=p;
        }
        updcnt(p);
    }
    inline void merge(pnode&p,pnode l,pnode r){
        if(!l){
            p=r;
            return;
        }
        if(!r){
            p=l;
            return;
        }
        if(l->pri<r->pri){
            merge(r->l,l,r->l);
            p=r;
        }else{
            merge(l->r,l->r,r);
            p=l;
        }
        updcnt(p);
    }
    pnode root=0;
    inline void insert(pnode&p,pnode t){
        if(!p){
            p=t;
            return;
        }
        if(t->pri<p->pri){
            if(p->val<t->val){
                insert(p->r,t);
            }else{
                insert(p->l,t);
            }
        }else{
            split(p,t->l,t->r,t->val);
            p=t;
        }
        updcnt(p);
    }
    inline void insert(int val){
        pnode t=new Node(val);
        insert(root,t);
    }
    pnode tt1,tt2;
    inline void erase(pnode&p,int val){
        if(!p)return;
        if(p->val==val){
            tt1=p->l,tt2=p->r;
            delete p;
            merge(p,tt1,tt2);
        }else if(val<p->val){
            erase(p->l,val);
        }else{
            erase(p->r,val);
        }
        updcnt(p);
    }
    inline void erase(int val){
        erase(root,val);
    }
    inline lint query(pnode p,int k){
        if(!p||k<=0)return 0;
        if(1+getcnt(p->r)<=k){
            return getsum(p->r)+p->val+query(p->l,k-1-getcnt(p->r));
        }
        return query(p->r,k);
    }
    inline lint query(int k){
        return query(root,k);
    }
    inline void clear(pnode p){
        if(!p)return;
        clear(p->l);
        delete p;
        clear(p->r);
    }
    inline void clear(){
        clear(root);
        root=0;
    }
    void debug(pnode p){
        if(!p)return;
        debug(p->l);
        cerr<<p->val<<" ";
        debug(p->r);
    }
    void debug(){
        cerr<<"debug :: ";
        debug(root);
        cerr<<" :: end of debug\n";
    }
}tr;

int L,R;

int startopt,endopt,inc;
lint best,canmake;
void dnc(int l,int r,int optl,int optr,bool ty=0){
    if(r<l)return;
    #define mid (l+r>>1)
    if(!ty){
        startopt=optr;
        endopt=optl;
        inc=-1;
    }else{
        startopt=optl;
        endopt=optr;
        inc=1;
    }
    while(R<mid){
        tr.insert(a[++R]);
    }
    while(startopt<L){
        tr.insert(a[--L]);
    }
    while(mid<R){
        tr.erase(a[R--]);
    }
    while(L<startopt){
        tr.erase(a[L++]);
    }
    #define movesleft(idx) (d-2*(s-(idx))-(mid-s))
    int opt=startopt;
    best=tr.query(movesleft(opt));
    ans=max(ans,best);
    for(int i=startopt+inc;(startopt<=i&&i<=endopt)||(endopt<=i&&i<=startopt);i+=inc){
        if(inc==-1)tr.insert(a[i]);
        else tr.erase(a[i-1]);
        L+=inc;
        canmake=tr.query(movesleft(i));
        if(best<canmake){
            opt=i;
            best=canmake;
            ans=max(ans,best);
        }
    }
    if(!ty){
        dnc(l,mid-1,optl,opt,1);
        dnc(mid+1,r,opt,optr,1);
    }else{
        dnc(mid+1,r,opt,optr);
        dnc(l,mid-1,optl,opt);
    }
}

lint findMaxAttraction(int N, int S, int D, int attraction[]) {
    n=N,s=S,d=D;
    for(int i=0;i<n;i++)a[i]=attraction[i];
    L=s,R=s-1;
    dnc(s,n-1,0,s);
    for(int i=0;i<n-i-1;i++){
        swap(a[i],a[n-i-1]);
    }
    tr.clear();
    L=s,R=s-1;
    s=n-s-1;
    dnc(s,n-1,0,s);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void dnc(int, int, int, int, bool)':
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:159:13: note: in expansion of macro 'mid'
  159 |     while(R<mid){
      |             ^~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:165:11: note: in expansion of macro 'mid'
  165 |     while(mid<R){
      |           ^~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:171:44: note: in expansion of macro 'mid'
  171 |     #define movesleft(idx) (d-2*(s-(idx))-(mid-s))
      |                                            ^~~
holiday.cpp:173:19: note: in expansion of macro 'movesleft'
  173 |     best=tr.query(movesleft(opt));
      |                   ^~~~~~~~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:171:44: note: in expansion of macro 'mid'
  171 |     #define movesleft(idx) (d-2*(s-(idx))-(mid-s))
      |                                            ^~~
holiday.cpp:179:26: note: in expansion of macro 'movesleft'
  179 |         canmake=tr.query(movesleft(i));
      |                          ^~~~~~~~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:187:15: note: in expansion of macro 'mid'
  187 |         dnc(l,mid-1,optl,opt,1);
      |               ^~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:188:13: note: in expansion of macro 'mid'
  188 |         dnc(mid+1,r,opt,optr,1);
      |             ^~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:190:13: note: in expansion of macro 'mid'
  190 |         dnc(mid+1,r,opt,optr);
      |             ^~~
holiday.cpp:149:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |     #define mid (l+r>>1)
      |                  ~^~
holiday.cpp:191:15: note: in expansion of macro 'mid'
  191 |         dnc(l,mid-1,optl,opt);
      |               ^~~

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