Submission #1053177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053177		hirayuu_oj	Radio Towers (IOI22_towers)	C++17	56 / 100	779 ms	11464 KiB

towers

#include "towers.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll INF=1LL<<60;
struct SegTree {
    vector<int> tree;
    int size;
    SegTree(int sz) {
        tree.resize(sz*2,0);
        size=sz;
    }
    void resize(int sz) {
        tree.resize(sz*2,0);
        size=sz;
    }
    void set(int p,int v) {
        p+=size;
        tree[p]=v;
        p/=2;
        while(p>=1) {
            tree[p]=max(tree[p*2],tree[p*2+1]);
            p/=2;
        }
    }
    int prod(int l,int r) {
        int ret=0;
        l+=size;
        r+=size;
        while(l<r) {
            if(l&1) {
                ret=max(ret,tree[l]);
                l++;
            }
            if(r&1) {
                r--;
                ret=max(ret,tree[r]);
            }
            l/=2;
            r/=2;
        }
        return ret;
    }
};
bool flg=false;
vector<int> h;
int n;
SegTree seg(0);
vector<int> lf;
vector<int> hr;
vector<int> ri;
vector<vector<int>> dbl;
void init(int N, std::vector<int> H) {
    h=H;
    n=N;
    seg.resize(N);
    rep(i,N) {
        seg.set(i,H[i]);
    }
}
void init_by_d(int d) {
    lf.resize(n+1,n);
    hr.resize(n+1,n);
    ri.resize(n+1,n);
    dbl.resize(20,vector<int>(n+1,0));
    rep(i,n) {
        int ok,ng;
        ok=-1;
        ng=i;
        while(abs(ok-ng)>1) {
            int mid=(ok+ng)/2;
            if(seg.prod(mid,i)>=h[i]+d)ok=mid;
            else ng=mid;
        }
        int l=ok;
        ok=n;
        ng=i;
        while(abs(ok-ng)>1) {
            int mid=(ok+ng)/2;
            if(seg.prod(i,mid+1)>=h[i]+d)ok=mid;
            else ng=mid;
        }
        if(l!=-1) {
            lf[l]=min(lf[l],ok);
            hr[l]=min(hr[l],i);
        }
        ri[i]=ok;
    }
    rrep(i,n) {
        lf[i]=min(lf[i],lf[i+1]);
        ri[i]=min(ri[i],ri[i+1]);
        hr[i]=min(hr[i],hr[i+1]);
    }
    dbl[0]=lf;
    rng(i,1,20) {
        rep(j,n+1) {
            dbl[i][j]=dbl[i-1][dbl[i-1][j]];
        }
    }
}

int max_towers(int L, int R, int D) {
    if(!flg) {
        flg=true;
        init_by_d(D);
    }
    if(R<ri[L])return 1;
    int pos=ri[L];
    int ans=1;
    rrep(i,20) {
        if(dbl[i][pos]<=R) {
            ans+=1<<i;
            pos=dbl[i][pos];
        }
    }
    if(hr[pos]<=R)ans++;
    return ans;
}

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