제출 #1023033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023033		vjudge1	송신탑 (IOI22_towers)	C++17	37 / 100	4098 ms	25032 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>

const int MAX=2e5+10;
const int inf=1e9;

struct segtree{
    int mx[4*MAX],mn[4*MAX],pmx[4*MAX];

    void build(int v,int tl,int tr,vector<int> &H){
        if(tl==tr){
            mx[v]=mn[v]=H[tl];
            pmx[v]=tl;
            return;
        }
        int tm=(tl+tr)/2;
        build(2*v,tl,tm,H);
        build(2*v+1,tm+1,tr,H);
        mx[v]=max(mx[2*v],mx[2*v+1]);
        if(mx[2*v]>mx[2*v+1])pmx[v]=pmx[2*v];
        else pmx[v]=pmx[2*v+1];
        mn[v]=min(mn[2*v],mn[2*v+1]);
    }

    int getMn(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return inf;
        if(l<=tl&&tr<=r)return mn[v];
        int tm=(tl+tr)/2;
        return min(getMn(2*v,tl,tm,l,r),getMn(2*v+1,tm+1,tr,l,r));
    }

    pii getMx(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return {-inf,-inf};
        if(l<=tl&&tr<=r)return {mx[v],pmx[v]};
        int tm=(tl+tr)/2;
        return max(getMx(2*v,tl,tm,l,r),getMx(2*v+1,tm+1,tr,l,r));
    }
}T;

int n,root;
vector<int> g[MAX];
int p[MAX];
int posMx=0;
bool sub;
vector<int> h;

int make_tree(int l,int r){
    if(l>r)return -1;
    auto [mx,pos]=T.getMx(1,0,n-1,l,r);
    int pos1=make_tree(l,pos-1);
    int pos2=make_tree(pos+1,r);
    if(pos1!=-1){
        g[pos].pb(pos1);
    }
    if(pos2!=-1)g[pos].pb(pos2);
    return pos;
}

void init(int N, vector<int> H) {

    sub=1;
    int cnt=0;
    for(int i=1;i<N-1;i++){
        if(H[i]>H[i-1]&&H[i]<H[i+1])cnt++;
    }
    if(N>1){
        cnt+=(H[1]>H[0]);
        cnt+=(H[N-2]<H[N-1]);
    }
    if(cnt!=1)sub=0;
    for(int i=0;i<N;i++){
        if(H[i]>H[posMx])posMx=i;
    }
    h=H;

    T.build(1,0,N-1,H);
    n=N;
    root=make_tree(0,n-1);
    p[0]=g[0].empty();
    for(int i=1;i<N;i++)p[i]=p[i-1]+(g[i].empty());
}

int get(int l,int r,int d,int g){
    if(l>r)return 0;
    int ans=0;
    if(T.getMn(1,0,n-1,l,r)<=g){
        ans=1;
    }
    auto [mx,pos]=T.getMx(1,0,n-1,l,r);
    ans=max(ans,get(l,pos-1,d,mx-d)+get(pos+1,r,d,mx-d));
    return ans;
}

int get1(int l,int r){
    if(l==r)return 1;
    int ans=p[r]-(l>0?p[l-1]:0);
    if(sz(g[l])==1&&g[l][0]<l)ans++;
    if(sz(g[r])==1&&g[r][0]>r)ans++;
    return ans;
}

int max_towers(int L, int R, int D) {
    if(sub){
        if(L<posMx&&posMx<R){
            if(h[posMx]-D>=max(h[L],h[R]))return 2;
            return 1;
        }
        else return 1;
    }
    if(D==1){
        return get1(L,R);
    }
    return get(L,R,D,inf);
}

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