제출 #1066085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066085		noyancanturk	휴가 (IOI14_holiday)	C++17	47 / 100	962 ms	65536 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*;
    int getcnt(pnode p){
        if(p)return p->cnt;
        return 0;
    }
    lint getsum(pnode p){
        if(p)return p->sum;
        return 0;
    }
    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);
        }
    }
    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);
    }
    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;
    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);
    }
    void insert(int val){
        pnode t=new Node(val);
        insert(root,t);
    }
    void erase(pnode&p,int val){
        if(!p)return;
        if(p->val==val){
            merge(p,p->l,p->r);
        }else if(val<p->val){
            erase(p->l,val);
        }else{
            erase(p->r,val);
        }
        updcnt(p);
    }
    void erase(int val){
        erase(root,val);
    }
    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);
    }
    lint query(int k){
        return query(root,k);
    }
    void clear(pnode p){
        if(!p)return;
        clear(p->l);
        delete p;
        clear(p->r);
    }
    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;

void dnc(int l,int r,int optl,int optr,bool ty=0){
    if(r<l)return;
    int mid=l+r>>1;
    int startopt,endopt,inc;
    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;
    lint 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;
        lint 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;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'void dnc(int, int, int, int, bool)':
holiday.cpp:144:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |     int mid=l+r>>1;
      |             ~^~

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