oj.uz

Submission #861578

# Submission time Handle Problem Language Result Execution time Memory
861578 2023-10-16T13:47:37 Z sunwukong123 Holiday (IOI14_holiday) C++14
100 / 100
 1781 ms 64052 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
map<int,int>disc;
struct node {
    int s,e,m,sum,num;
    node *l, *r;
    node(int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        sum=num=0;
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void set(int x, int nval, int value){
        //debug(x,nval,value);
        if(s==e){
            if(nval==1){
                num++;
                sum+=value;
            } else{
                num--;
                sum-=value;
            }
            return;
        }
        if(x<=m)l->set(x,nval,value);
        else r->set(x,nval,value);
        sum=l->sum+r->sum;
        num=l->num+r->num;
    }
    int kth(int x){
        if(x==0)return 0;
        if(s==e){
            //debug(sum);
            if(x)return sum;
            else return 0;
        }
        if(r->num>=x){
            return r->kth(x);
        } else {
            return r->sum + l->kth(x - r->num);
        }
    }
}*seg;
/*


*/
int A[250005];
int L[250005], R[250005];
int start;
int lidx, ridx;
void fit(int lf, int rg){
    while(ridx>rg){
        seg->set(disc[ridx],-1,A[ridx]);
        ridx--;
    }
    while(ridx<rg){
        ++ridx;
        seg->set(disc[ridx],1,A[ridx]);
    }
    while(lidx<lf){
        seg->set(disc[lidx],-1,A[lidx]);
        lidx++;
    }
    while(lidx>lf){
        --lidx;
        seg->set(disc[lidx],1,A[lidx]);
    }

    
}
void dncR(int s, int e, int optl, int optr){ 
    if(s>e)return;
    if(optl>optr)return;
    int energy=(s+e)/2; // what if we have x energy?
    pair<int,int> opt={0,optl};
    for(int i=optl;i<=optr;i++){
        fit(start,i);
        int dist=i-start;
        if(energy>dist){
            int val=seg->kth(energy-dist);
            //debug(energy,dist,i,val);
            R[energy]=max(R[energy],val);
            opt=max(opt,{val,i});
        } else{
            break;
        }
        
    }

    dncR(energy+1,e,opt.second,optr);

    dncR(s,energy-1,optl,opt.second);
    
}
void dncL(int s, int e, int optl, int optr){ 
    if(s>e)return;
    if(optl>optr)return;
    int energy=(s+e)/2; // what if we have x energy?
    pair<int,int> opt={0,-optr};
    for(int i=optr;i>=optl;i--){
        fit(i,start-1);
        int dist=start-i;
        if(energy>2*dist){
            int val=seg->kth(energy-2*dist);
            L[energy]=max(L[energy],val);
            opt=max(opt,{val,-i});
        } else{
            break;
        }
        
    }

    dncL(energy+1,e,optl,-opt.second);

    dncL(s,energy-1,-opt.second,optr);
    
}

int solve(int n, int d){
    //assume that going left cost 2 days, going right cost 1 day
    seg=new node(0,n);
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    lidx=0,ridx=0;
    dncR(0,d,start,n);
    lidx=0,ridx=0;
    seg=new node(0,n);
    dncL(0,d,1,start-1);
    int ans=0;
    for(int i=0;i<=d;i++){
        //debug(i,L[i],R[i]);
        ans=max(ans,R[i]+L[d-i]);
    }
    return ans;
}

int findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
    ++start;
    ::start=start;
   
    for(int i=1;i<=n;i++)A[i]=attraction[i-1];
    vector<pi> vec;
    for(int i=1;i<=n;i++)vec.push_back({A[i],i});
    sort(vec.begin(),vec.end());
    for(int i=0;i<(int)vec.size();i++){
        disc[vec[i].second]=i+1;
    }
    int ans=solve(n,d);
    ::start=n-::start+1;
    reverse(A+1,A+n+1);
    vec.clear();
    for(int i=1;i<=n;i++)vec.push_back({A[i],i});
    sort(vec.begin(),vec.end());
    for(int i=0;i<(int)vec.size();i++){
        disc[vec[i].second]=i+1;
    }

    ans=max(ans,solve(n,d));
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4932 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1497 ms 63444 KB Output is correct
2 Correct 953 ms 63500 KB Output is correct
3 Correct 1527 ms 63448 KB Output is correct
4 Correct 980 ms 63472 KB Output is correct
5 Correct 1479 ms 58584 KB Output is correct
6 Correct 452 ms 21392 KB Output is correct
7 Correct 815 ms 34620 KB Output is correct
8 Correct 880 ms 41104 KB Output is correct
9 Correct 341 ms 16636 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6740 KB Output is correct
2 Correct 22 ms 6748 KB Output is correct
3 Correct 22 ms 6748 KB Output is correct
4 Correct 23 ms 6760 KB Output is correct
5 Correct 22 ms 6492 KB Output is correct
6 Correct 7 ms 5468 KB Output is correct
7 Correct 5 ms 5468 KB Output is correct
8 Correct 6 ms 5444 KB Output is correct
9 Correct 6 ms 5552 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1517 ms 63852 KB Output is correct
2 Correct 1595 ms 63860 KB Output is correct
3 Correct 319 ms 31268 KB Output is correct
4 Correct 15 ms 6704 KB Output is correct
5 Correct 5 ms 5468 KB Output is correct
6 Correct 7 ms 5444 KB Output is correct
7 Correct 6 ms 5468 KB Output is correct
8 Correct 1781 ms 64052 KB Output is correct
9 Correct 1748 ms 64028 KB Output is correct