oj.uz

Submission #969481

# Submission time Handle Problem Language Result Execution time Memory
969481 2024-04-25T08:29:40 Z boyliguanhan Holiday (IOI14_holiday) C++17
100 / 100
 401 ms 57584 KB 
#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],CC;
pair<II,II> V[100100];
struct node{
    int sum;
    II cnt,lc,rc;
    node(){lc=rc=sum=cnt=0;}
    node(int a,int b,int c,int d){
        sum=a,cnt=b,lc=c,rc=d;
    }
} T[1<<21];
int nn(int S){
    return T[++CC]=node(V[S-1].first,1,0,0),CC;
}
int nn(int lc,int rc){
    return T[++CC]=node(T[lc].sum+T[rc].sum,T[lc].cnt+T[rc].cnt,lc,rc),CC;
}
int nn(){
    return T[++CC]=node(),CC;
}
int RTL[100100],RTR[100100];
int query(int x,II need){
    if(!x) return 0;
    if(T[x].cnt<=need)
        return T[x].sum;
    if(T[T[x].rc].cnt>=need)
        return query(T[x].rc,need);
    return T[T[x].rc].sum+query(T[x].lc,need-T[T[x].rc].cnt);
}
int update(int rt,int l,int r,int pos){
    if(l==r)
        return nn(l);
    if(l+r>>1<pos)
        return nn(T[rt].lc,update(T[rt].rc,l+r+2>>1,r,pos));
    return nn(update(T[rt].lc,l,l+r>>1,pos),T[rt].rc);
}
int build(int l,int r){
    if(l==r)return nn();
    return nn(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);
}
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);
    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]);
    dpL(1,d,0,start,start);
    for(int i=1;i<=CC;i++)
        T[i]=node();
    CC=0;
    RTR[start]=build(1,n);
    for(int i=start;++i<n;)
        RTR[i]=update(RTR[i-1],1,n,indd[i]);
    dpR(1,d,start,n-1,start);
    for(int i=1;i<=CC;i++)
        T[i]=node();
    CC=0;
    int ANS=0;
    for(int i=0;i<=d;i++)
        ANS=max(ANS,valL[i]+valR[d-i]);
    start=n-1-start;
    reverse(arr,arr+n);
    return ANS;
}
int findMaxAttraction(II n, II start, II d, II attraction[]) {
    return max(proc(n,start,d,attraction),proc(n,start,d,attraction));
}
#undef int
#undef II

Compilation message

holiday.cpp: In function 'long long int update(long long int, long long int, long long int, long long int)':
holiday.cpp:38:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     if(l+r>>1<pos)
      |        ~^~
holiday.cpp:39:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         return nn(T[rt].lc,update(T[rt].rc,l+r+2>>1,r,pos));
      |                                            ~~~^~
holiday.cpp:40:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     return nn(update(T[rt].lc,l,l+r>>1,pos),T[rt].rc);
      |                                 ~^~
holiday.cpp: In function 'long long int build(long long int, long long int)':
holiday.cpp:44:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     return nn(build(l,l+r>>1),build(l+r+2>>1,r));
      |                       ~^~
holiday.cpp:44:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     return nn(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:48:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     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:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 56408 KB Output is correct
2 Correct 9 ms 56664 KB Output is correct
3 Correct 10 ms 56412 KB Output is correct
4 Correct 10 ms 56412 KB Output is correct
5 Correct 10 ms 56412 KB Output is correct
6 Correct 9 ms 56456 KB Output is correct
7 Correct 10 ms 56408 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 56900 KB Output is correct
2 Correct 111 ms 56900 KB Output is correct
3 Correct 340 ms 56908 KB Output is correct
4 Correct 175 ms 56668 KB Output is correct
5 Correct 351 ms 56920 KB Output is correct
6 Correct 103 ms 56792 KB Output is correct
7 Correct 195 ms 56844 KB Output is correct
8 Correct 212 ms 56668 KB Output is correct
9 Correct 74 ms 56752 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 56668 KB Output is correct
2 Correct 13 ms 56412 KB Output is correct
3 Correct 13 ms 56412 KB Output is correct
4 Correct 15 ms 56412 KB Output is correct
5 Correct 14 ms 56408 KB Output is correct
6 Correct 11 ms 56412 KB Output is correct
7 Correct 11 ms 56412 KB Output is correct
8 Correct 10 ms 56412 KB Output is correct
9 Correct 10 ms 56412 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 57580 KB Output is correct
2 Correct 401 ms 57584 KB Output is correct
3 Correct 67 ms 56940 KB Output is correct
4 Correct 13 ms 56424 KB Output is correct
5 Correct 10 ms 56420 KB Output is correct
6 Correct 10 ms 56520 KB Output is correct
7 Correct 10 ms 56416 KB Output is correct
8 Correct 287 ms 57340 KB Output is correct
9 Correct 285 ms 57180 KB Output is correct