Submission #1144422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144422		Noproblem29	Giraffes (JOI22_giraffes)	C++20	100 / 100	1760 ms	4340 KiB

giraffes

#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=8005;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e9;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
struct ki{
    int x,y,w;
    ki():x(0),y(0),w(0){}
    ki(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
};
struct BIT{
    int sz;
    vector<int>f;
    BIT():sz(0),f(vector<int>()){}
    BIT(int n){
        sz=1;
        while(sz<n){
            sz*=2ll;
        }
        f=vector<int>(sz*2,INF*2);
    }
    void clean(){
        for(int i=0;i<sz*2;i++){
            f[i]=INF*2;
        }
    }
    void upd(int l,int x){
        l+=sz;
        f[l]=min(f[l],x);
        while(l>1){
            l>>=1;
            f[l]=min(f[l*2],f[l*2+1]);
        }
    }
    int get(int l,int r){
        int res=INF*2;
        l+=sz;
        r+=sz;
        while(l!=r){
            if(l&1)res=min(res,f[l++]);
            if(r&1)res=min(res,f[--r]);
            l>>=1;
            r>>=1;
        }
        return res;
    }
};
int n,m;
int p[N];
int dp[4][N];
vector<int>p1,p2;

void test(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>p[i];
        p[i]--;
        p1.push_back(i);
        p2.push_back(i);
    }
    sort(p1.begin(),p1.end(),[](int x,int y){
        return x-p[x]<y-p[y];
    });
    sort(p2.begin(),p2.end(),[](int x,int y){
        return x+p[x]<y+p[y];
    });
    int ans=n-1;
    BIT st1(n),st2(n);
    while(ans>=1){
        vector<ki>v,v1,v2;
        for(int mask=0;mask<4;mask++){
            for(int i=0;i<n;i++){
                if(dp[mask][i]!=INF){
                    int x=i-(mask&2?dp[mask][i]:0);
                    int y=p[i]-(mask&1?dp[mask][i]:0);
                    v.push_back({x,y,dp[mask][i]});
                }
                dp[mask][i]=INF;
            }
        }
        v1=v;
        v2=v;
        m=v.size();
        sort(v1.begin(),v1.end(),[](const ki&a,const ki&b){
            return a.x-a.y<b.x-b.y;
        });
        sort(v2.begin(),v2.end(),[](const ki&a,const ki&b){
            return a.x+a.y+a.w<b.x+b.y+b.w;
        });
        
        int posp=0,posv=0;
        // i hate conditions
        st1.clean();
        st2.clean();
        posp=0;
        posv=0;
        while(posp!=n||posv!=m){
            int px=p1[posp],py=p[px];
            int res1=(posp!=n?px-py:INF);
            int res2=(posv!=m?v1[posv].x-v1[posv].y:INF);
            if(res1>=res2){
                st1.upd(v1[posv].x,v1[posv].y+v1[posv].w);
                st2.upd(v1[posv].y+v1[posv].w,-v1[posv].x);
                posv++;
            }
            else{
                dp[0][px]=min(dp[0][px],st1.get(px+1,n)-py);    
                dp[3][px]=min(dp[3][px],px-(-st2.get(0,py)));
                posp++;
            }
        }   
        // still hating
        st1.clean();
        st2.clean();
        posp=n-1;
        posv=m-1;
        while(posp!=-1||posv!=-1){
            int px=p1[posp],py=p[px];
            int res1=(posp!=-1?px-py:-INF);
            int res2=(posv!=-1?v1[posv].x-v1[posv].y:-INF);
            if(res1<=res2){
                st1.upd(v1[posv].y,v1[posv].x+v1[posv].w);
                st2.upd(v1[posv].x+v1[posv].w,-v1[posv].y);
                posv--;
            }
            else{
                dp[0][px]=min(dp[0][px],st1.get(py+1,n)-px);
                dp[3][px]=min(dp[3][px],py-(-st2.get(0,px)));
                posp--;
            }
        }  
        //wtf author
        st1.clean();
        st2.clean();
        posp=0;
        posv=0;
        while(posp!=n||posv!=m){
            int px=p2[posp],py=p[px];
            int res1=(posp!=n?px+py:INF);
            int res2=(posv!=m?v2[posv].x+v2[posv].y+v2[posv].w:INF);
            if(res1>=res2){
                st1.upd(v2[posv].x,-v2[posv].y);
                st2.upd(v2[posv].y,-v2[posv].x);
                posv++;
            }
            else{
                dp[1][px]=min(dp[1][px],py-(-st1.get(px+1,n)));
                dp[2][px]=min(dp[2][px],px-(-st2.get(py+1,n)));
                posp++;
            }
        }   
        // blyaaaaaaaaaaaaa 
        st1.clean();
        st2.clean();
        posp=n-1;
        posv=m-1;
        while(posp!=-1||posv!=-1){
            int px=p2[posp],py=p[px];
            int res1=(posp!=-1?px+py:-INF);
            int res2=(posv!=-1?v2[posv].x+v2[posv].y+v2[posv].w:-INF);
            if(res1<=res2){
                st1.upd(v2[posv].y+v2[posv].w,v2[posv].x+v2[posv].w);
                st2.upd(v2[posv].x+v2[posv].w,v2[posv].y+v2[posv].w);

                posv--;
            }
            else{
                dp[1][px]=min(dp[1][px],st1.get(0,py)-px);
                dp[2][px]=min(dp[2][px],st2.get(0,px)-py);
                posp--;
            }
        }  

        bool ok=1;
        for(int mask=0;mask<4;mask++){
            for(int i=0;i<n;i++){
                int lx=(mask&2?i:n-i-1);
                int rx=(mask&1?p[i]:n-p[i]-1);
                if(dp[mask][i]>min(lx,rx)){
                    dp[mask][i]=INF;
                }
                if(dp[mask][i]!=INF){
                    ok=0;
                }
            }
        }
        if(ok){
            break;
        }

        ans--;
    }
    cout<<ans<<'\n';

}



/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41