Submission #969443

#	Time	Username	Problem	Language	Result	Execution time	Memory
969443		vjudge1	휴가 (IOI14_holiday)	C++17	0 / 100	64 ms	65536 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
#define II signed
#define int long long
using namespace std;
int valL[250100],valR[250100];
II indd[100100];
pair<II,II> V[100100];
struct node{
    int sum;
    II cnt;
    node *lc,*rc;
    node(){lc=rc=0,sum=cnt=0;}
    node(int S){cnt=1,sum=V[S-1].first,lc=rc=0;}
    node(node*a,node*b){
        lc=a,rc=b;
        cnt=a->cnt+b->cnt;
        sum=a->sum+b->sum;
    }
} *RTL[100100],*RTR[100100];
int query(node*x,II need){
    if(!x) return 0;
    if(x->cnt<=need)
        return x->sum;
    if(x->rc->cnt>=need)
        return query(x->rc,need);
    return x->rc->sum+query(x->lc,need-x->rc->cnt);
}
node*update(node*rt,int l,int r,int pos){
    if(l==r)
        return new node(l);
    if(l+r>>1<pos)
        return new node(rt->lc,update(rt->rc,l+r+2>>1,r,pos));
    return new node(update(rt->lc,l,l+r>>1,pos),rt->rc);
}
node*build(int l,int r){
    if(l==r)return new node();
    return new node(build(l,l+r>>1),build(l+r+2>>1,r));
}
void dpL(int l,int r,int optl, int optr, int start){
    if(l>r) return;
    int mid=l+r>>1;
    int optmid=optl;
    for(int i=optl;i<=optr;i++)
        if(2*(start-i)<mid) {
            int cost=query(RTL[i],mid-2*(start-i));
            if(valL[mid]<cost)
                valL[mid]=cost,optmid=i;
        }
    dpL(l,mid-1,optmid,optr,start);
    dpL(mid+1,r,optl,optmid,start);
}
void dpR(int l,int r,int optl, int optr, int start){
    if(l>r) return;
    int mid=l+r>>1;
    int optmid=optl;
    for(int i=optl;i<=optr;i++)
        if(i-start<mid) {
            int cost=query(RTR[i],mid-i+start);
            if(valR[mid]<cost)
                valR[mid]=cost,optmid=i;
        }
    dpR(l,mid-1,optl,optmid,start);
    dpR(mid+1,r,optmid,optr,start);
}
void DEL(node*rt){
    if(!rt)return;
    DEL(rt->lc);
    DEL(rt->rc);
    delete rt;
}
int proc(II n, II &start, II d,II arr[]){
    memset(valL,0,sizeof valL);
    memset(valR,0,sizeof valR);
    memset(indd,0,sizeof indd);
    for(int i=0;i<n;i++)
        V[i]=make_pair(arr[i],i);
    RTL[start+1]=build(1,n);
    RTR[start]=build(1,n);
    sort(V,V+n);
    for(int i=0;i<n;i++)
        indd[V[i].second]=i+1;
    for(int i=start+1;i--;)
        RTL[i]=update(RTL[i+1],1,n,indd[i]);
    for(int i=start;++i<n;)
        RTR[i]=update(RTR[i-1],1,n,indd[i]);
    dpL(1,d,0,start,start);
    dpR(1,d,start,n-1,start);
    int ANS=0;
    for(int i=0;i<=d;i++)
        ANS=max(ANS,valL[i]+valR[d-i]);
    reverse(arr,arr+n);
    start=n-1-start;
    for(int i=0;i<start+2;i++)
        DEL(RTL[i]);
    for(int i=start;i<n;i++)
        DEL(RTR[i]);
    return ANS;
}
int findMaxAttraction(II n, II start, II d, II attraction[]) {
    return max(proc(n,start,d,attraction),proc(n,start,d,attraction));
}

Compilation message (stderr)

holiday.cpp: In function 'node* update(node*, long long int, long long int, long long int)':
holiday.cpp:32:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     if(l+r>>1<pos)
      |        ~^~
holiday.cpp:33:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         return new node(rt->lc,update(rt->rc,l+r+2>>1,r,pos));
      |                                              ~~~^~
holiday.cpp:34:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     return new node(update(rt->lc,l,l+r>>1,pos),rt->rc);
      |                                     ~^~
holiday.cpp: In function 'node* build(long long int, long long int)':
holiday.cpp:38:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     return new node(build(l,l+r>>1),build(l+r+2>>1,r));
      |                             ~^~
holiday.cpp:38:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     return new node(build(l,l+r>>1),build(l+r+2>>1,r));
      |                                           ~~~^~
holiday.cpp: In function 'void dpL(long long int, long long int, long long int, long long int, long long int)':
holiday.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid=l+r>>1;
      |             ~^~
holiday.cpp: In function 'void dpR(long long int, long long int, long long int, long long int, long long int)':
holiday.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid=l+r>>1;
      |             ~^~

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