Submission #626359

#	Time	Username	Problem	Language	Result	Execution time	Memory
626359		whynotshadow	Radio Towers (IOI22_towers)	C++17	11 / 100	4091 ms	2864 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
//#include <cassert>
//#include <cstdio>
#define ll int
//#include <vector>
using namespace std;
vector<ll>v;
const ll N=1e5+9;
const ll INF=1e9;
ll tr[4*N],sz,szz,k,fll;
void build(ll x, ll l_x, ll r_x){
    if(l_x==r_x) tr[x]=v[l_x-1];
    else{
        ll mid=(l_x+r_x)>>1;
        build(x<<1,l_x,mid);
        build(x<<1|1,mid+1,r_x);
        tr[x]=max(tr[x<<1],tr[x<<1|1]);
    }
}
ll GET(ll x, ll l_x, ll r_x, ll l, ll r){
    if(l_x>r || l>r_x) return -INF;
    if(l<=l_x && r_x<=r) return tr[x];
    ll mid=(l_x+r_x)>>1;
    return max(GET(x<<1,l_x,mid,l,r),GET(x<<1|1,mid+1,r_x,l,r));
}
void init(int N, std::vector<int> H) {
    for(auto to:H){
        v.push_back(to);
    }
    sz=1ll;
    while(sz<N) sz<<=1;
    build(1ll,1ll,sz);
    k=0,fll=0;
    for(int i=1; i<N; i++){
        if(v[i]>v[i-1]) szz=i;
        else fll=1;
        if(fll==1 && v[i]<=v[i-1]) k=1;
    }
}

int max_towers(int L, int R, int D) {
    if(k==0){
        if(L<=szz && szz<=R && v[L]<=v[szz]-D && v[R]<=v[szz]-D) return 2;
        return 1;
    }
    vector<pair<ll,ll>>cur,anss;
    for(int i=L; i<=R; i++){
        cur.push_back(make_pair(v[i],i));
    }
    sort(cur.begin(),cur.end());
    for(auto [to,it]:cur){
        bool fl=0;
        for(auto [to2,it2]:anss){
            ll res=GET(1,1,sz,min(it,it2)+2,max(it,it2))-D;
            if(res>=to && res>=to2 && abs(it-it2)!=1) fl=0;
            else{
                fl=1;
                break;
            }
        }
        if(fl==0) anss.push_back(make_pair(to,it));
    }
    return anss.size();
//    return 0;
}

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