oj.uz

Submission #776176

# Submission time Handle Problem Language Result Execution time Memory
776176 2023-07-07T11:13:23 Z alvingogo Holiday (IOI14_holiday) C++14
100 / 100
 358 ms 51020 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
using namespace std;

struct PST{
    struct no{
        int lch=-1,rch=-1;
        int val=0;
        long long v2=0;
    };
    vector<no> st;
    PST(){
        st.resize(2005000);
    }
    int nw=1;
    void build(int v,int L,int R){
        if(L==R){
            return;
        }
        st[v].lch=nw;
        nw++;
        st[v].rch=nw;
        nw++;
        int m=(L+R)/2;
        build(st[v].lch,L,m);
        build(st[v].rch,m+1,R);
    }
    void update(int L,int R,int fr,int &to,int p,int t,int t2){
        to=nw;
        st[nw]=st[fr];
        st[nw].val+=t;
        st[nw].v2+=t2;
        nw++;
        if(L==R){
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(L,m,st[fr].lch,st[to].lch,p,t,t2);
        }
        else{
            update(m+1,R,st[fr].rch,st[to].rch,p,t,t2);
        }
    }
    long long query(int L,int R,int fr,int to,int k){
        if(L==R){
            return st[to].v2-st[fr].v2;
        }
        int sum=st[st[to].rch].val-st[st[fr].rch].val;
        int m=(L+R)/2;
        if(sum>=k){
            return query(m+1,R,st[fr].rch,st[to].rch,k);
        }
        else{
            return query(L,m,st[fr].lch,st[to].lch,k-sum)+st[st[to].rch].v2-st[st[fr].rch].v2;
        }
    }
    vector<int> root;
    int n;
    void init(vector<int> a){
        n=a.size();
        nw=1;
        root.clear();
        vector<pair<int,int> > z(n);
        for(int i=0;i<n;i++){
            z[i]={a[i],i};
        }
        sort(z.begin(),z.end());
        for(int i=0;i<n;i++){
            a[i]=lower_bound(z.begin(),z.end(),pair<int,int>(a[i],i))-z.begin();
        }
        root.resize(n+1);
        root[0]=0;
        build(0,0,n-1);
        for(int i=1;i<=n;i++){
            update(0,n-1,root[i-1],root[i],a[i-1],1,z[a[i-1]].fs);
        }
    }
    long long ask(int l,int r,int k){
        if(k<=0){
            return 0;
        }
        k=min(k,r-l+1);
        long long u=query(0,n-1,root[l],root[r+1],k);
        return u;
    }
}pst;

int n,st,k;
long long ans=0;
void dc(int l,int r,int u,int d){
    if(l>r || u>d){
        return;
    }
    pair<long long,int> p(0,0);
    int m=(l+r)/2;
    for(int i=u;i<=d;i++){
        p=max(p,{pst.ask(st-m,st+i,k-2*m-i),-i});
    }
    ans=max(ans,p.fs);
    dc(l,m-1,-p.sc,d);
    dc(m+1,r,u,-p.sc);
}
void solve(vector<int> v){
    pst.init(v);
    //dp[i][j]=pst.ask(st-i,st+j,d-2*i-j);
    int a=st,b=n-st-1;
    dc(0,a,0,b);
}
long long findMaxAttraction(int _n, int _st, int _k, int at[]) {
    n=_n;
    k=_k;
    st=_st;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        v[i]=at[i];
    }
    solve(v);
    st=_n-_st-1;
    reverse(v.begin(),v.end());
    solve(v);
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47700 KB Output is correct
2 Correct 22 ms 47764 KB Output is correct
3 Correct 20 ms 47700 KB Output is correct
4 Correct 17 ms 47704 KB Output is correct
5 Correct 19 ms 47700 KB Output is correct
6 Correct 18 ms 47700 KB Output is correct
7 Correct 21 ms 47720 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 50132 KB Output is correct
2 Correct 105 ms 50264 KB Output is correct
3 Correct 104 ms 50292 KB Output is correct
4 Correct 103 ms 50356 KB Output is correct
5 Correct 108 ms 50124 KB Output is correct
6 Correct 41 ms 48444 KB Output is correct
7 Correct 63 ms 49112 KB Output is correct
8 Correct 74 ms 49360 KB Output is correct
9 Correct 33 ms 48308 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47748 KB Output is correct
2 Correct 20 ms 47836 KB Output is correct
3 Correct 19 ms 47800 KB Output is correct
4 Correct 27 ms 47856 KB Output is correct
5 Correct 21 ms 47792 KB Output is correct
6 Correct 22 ms 47708 KB Output is correct
7 Correct 19 ms 47688 KB Output is correct
8 Correct 19 ms 47676 KB Output is correct
9 Correct 19 ms 47700 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 50120 KB Output is correct
2 Correct 93 ms 50956 KB Output is correct
3 Correct 83 ms 49248 KB Output is correct
4 Correct 22 ms 47780 KB Output is correct
5 Correct 20 ms 47792 KB Output is correct
6 Correct 20 ms 47700 KB Output is correct
7 Correct 23 ms 47788 KB Output is correct
8 Correct 344 ms 50940 KB Output is correct
9 Correct 358 ms 51020 KB Output is correct