oj.uz

Submission #329578

# Submission time Handle Problem Language Result Execution time Memory
329578 2020-11-21T16:56:24 Z hoanghq2004 Holiday (IOI14_holiday) C++14
100 / 100
 557 ms 49508 KB 
//#define TIOJ
#ifdef TIOJ
#include "lib1899.h"
#else
#include "holiday.h"
#endif

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int maxn=100000+5;
const int maxnode=2000000;
const int INF=(1LL<<60);
struct Node
{
    int lc,rc,size;
    LL Sum;
    Node() {Sum=size=lc=rc=0;}
};
vector<int> disc;
int root[maxn],pmem;
Node mem[maxnode];
int newnode(Node& last)
{
    Node& now=mem[pmem];
    now.lc=last.lc,now.rc=last.rc;
    now.Sum=last.Sum,now.size=last.size;
    return pmem++;
}
void pull(Node& now)
{
    now.Sum=mem[now.lc].Sum+mem[now.rc].Sum;
    now.size=mem[now.lc].size+mem[now.rc].size;
}
void insert(int last,int& cur,int L,int R,LL num)
{  
    cur=newnode(mem[last]);
    Node& now=mem[cur];
    if(L==R) {now.Sum+=disc[num],now.size++;return;}
    LL M=(L+R)>>1;
    if(num<=M) insert(mem[last].lc,now.lc,L,M,num);
    else insert(mem[last].rc,now.rc,M+1,R,num);
    pull(now);
}
LL query(int lt,int rt,LL L,LL R,LL k)
{
    if(L==R) return (LL)disc[L] * min( k ,(LL) mem[rt].size - mem[lt].size );
    LL M=(L+R)>>1,rsize= mem[mem[rt].rc].size - mem[mem[lt].rc].size,rsum=mem[mem[rt].rc].Sum-mem[mem[lt].rc].Sum;
    if(rsize >=k) return query(mem[lt].rc,mem[rt].rc,M+1,R,k);
    return query(mem[lt].lc,mem[rt].lc,L,M,k-rsize)+rsum;
}
inline void buildSeg(int n,int attraction[])
{
    root[0]=0;pmem=1;
    for(LL i=1;i<=n;i++)
        insert(root[i-1],root[i],0,disc.size()-1,lower_bound(disc.begin(),disc.end(),attraction[i-1])-disc.begin());
}
LL solve(int start,int day,int L,int R,int optL,int optR)
{
    LL M=(L+R)>>1,optM=optL,ret=-INF;
    for(int i=optL;i<=optR;i++)
    {
        LL now=query(root[M],root[i+1],0,disc.size()-1, day - (start-M + i-M) );
        if(now>ret) ret=now,optM=i;
    }
    if(L<=M-1) ret=max(ret,solve(start,day,L,M-1,optL,optM));
    if(M+1<=R) ret=max(ret,solve(start,day,M+1,R,optM,optR));
    return ret;
}
LL findMaxAttraction(int n,int start,int day,int attraction[])
{
    disc.clear();
    for(int i=0;i<n;i++) disc.push_back(attraction[i]);
    sort(disc.begin(),disc.end());
    disc.resize(unique(disc.begin(),disc.end())-disc.begin());

    buildSeg(n,attraction);
    LL ans =solve(start,day,0,start,start,n-1);
    
    start=n-start-1;reverse(attraction,attraction+n); 
    buildSeg(n,attraction);
    ans=max(ans,solve(start,day,0,start,start,n-1));    
    return ans;

}

Compilation message

holiday.cpp:13:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   13 | const int INF=(1LL<<60);
      |               ~~~~^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47340 KB Output is correct
2 Correct 26 ms 47340 KB Output is correct
3 Correct 28 ms 47340 KB Output is correct
4 Correct 26 ms 47340 KB Output is correct
5 Correct 26 ms 47340 KB Output is correct
6 Correct 26 ms 47340 KB Output is correct
7 Correct 27 ms 47340 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 48740 KB Output is correct
2 Correct 42 ms 48740 KB Output is correct
3 Correct 46 ms 48868 KB Output is correct
4 Correct 45 ms 48740 KB Output is correct
5 Correct 77 ms 48740 KB Output is correct
6 Correct 42 ms 47852 KB Output is correct
7 Correct 56 ms 48104 KB Output is correct
8 Correct 61 ms 48360 KB Output is correct
9 Correct 38 ms 47724 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47468 KB Output is correct
2 Correct 27 ms 47340 KB Output is correct
3 Correct 29 ms 47340 KB Output is correct
4 Correct 32 ms 47468 KB Output is correct
5 Correct 31 ms 47340 KB Output is correct
6 Correct 28 ms 47340 KB Output is correct
7 Correct 29 ms 47360 KB Output is correct
8 Correct 27 ms 47340 KB Output is correct
9 Correct 27 ms 47340 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49508 KB Output is correct
2 Correct 146 ms 49464 KB Output is correct
3 Correct 186 ms 48360 KB Output is correct
4 Correct 31 ms 47340 KB Output is correct
5 Correct 27 ms 47340 KB Output is correct
6 Correct 28 ms 47340 KB Output is correct
7 Correct 32 ms 47340 KB Output is correct
8 Correct 557 ms 49508 KB Output is correct
9 Correct 552 ms 49380 KB Output is correct