제출 #1219590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219590		ASGA_RedSea	송신탑 (IOI22_towers)	C++20	27 / 100	4062 ms	8732 KiB

towers

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

#include"towers.h"


int n,k=-1;
vector<int>h,vv;
map<int,int>val;


void init(int N,vector<int>H){
    n=N;h=H;

    {
        vv=h;
        sort(vv.begin(),vv.end());
        for(int i=0;i<vv.size();i++)val[vv[i]]=i;
    }

    int l=1,r=n-2;
    while(l<n&&h[l-1]<=h[l])l++;l--;
    while(r>=0&&h[r]>=h[r+1])r--;r++;
    if(l==r)k=l;
}

struct sgt{
    vector<int>s;
    int lg,sz;
    sgt(int N){
        lg=__lg(N)+1;
        sz=1<<lg;
        s.assign(sz*2,0);
    }

    void edit(int i,int v){
        i+=sz;s[i]=v;
        while(i>1){
            i>>=1;
            s[i]=max(s[i*2],s[i*2+1]);
        }
    }
    int get(int L,int R,int l,int r,int i){
        if(L>R||l>R||L>r)return 0;
        if(L<=l&&r<=R)return s[i];
        return max(get(L,R,l,(l+r)/2,i*2),get(L,R,(l+r)/2+1,r,i*2+1));
    }
    int get(int l){return get(++l,sz,1,sz,1);}
};
struct sgtt{
    vector<int>s;
    int lg,sz;
    sgtt(int N){
        lg=__lg(N)+1;
        sz=1<<lg;
        s.assign(sz*2,0);
    }

    void edit(int L,int R,int mx,int l,int r,int i){
        if(L>R||l>R||L>r)return;
        if(L<=l&&r<=R){s[i]=max(s[i],mx);return;}
        edit(L,R,mx,l,(l+r)/2,i*2);
        edit(L,R,mx,(l+r)/2+1,r,i*2+1);
    }
    void edit(int i,int mx){edit(i+1,sz,mx,1,sz,1);}
    int get(int i){
        i+=sz;
        int ret=0;
        while(i){
            ret=max(ret,s[i]);
            i>>=1;
        }
        return ret;
    }
};

int max_towers(int l,int r,int dd){
    if(k!=-1)return(l<=k&&k<=r&&max(h[l]+dd,h[r]+dd)<=h[k])+1;

    vector<int>d(n,0);

    sgt s(n+5);
    sgtt p(n+5);

    for(int i=l;i<=r;i++){
        int j=lower_bound(vv.begin(),vv.end(),h[i]+dd)-vv.begin();
        if(j==vv.size())d[i]=1;
        else{
            j=val[vv[j]];
            d[i]=s.get(j)+1;
            p.edit(j,d[i]);
        }
        s.edit(val[h[i]],p.get(val[h[i]]));
    }

    return *max_element(d.begin(),d.end());
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23