Submission #1022990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022990		vjudge1	송신탑 (IOI22_towers)	C++17	23 / 100	4101 ms	17864 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;

void init(int N, vector<int> H) {
    T.build(1,0,N-1,H);
    n=N;
}

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 max_towers(int L, int R, int D) {
    return get(L,R,D,inf);
}

• Subtask 1: 0 / 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