Submission #731611

#	Time	Username	Problem	Language	Result	Execution time	Memory
731611		PoonYaPat	Radio Towers (IOI22_towers)	C++17	17 / 100	1561 ms	90076 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int R[100010],L[100010],h[100010],n,s[1<<18];
vector<pii> v;

struct ss {
    int mmin,mmax,sl,sr;
} sg[1<<18]; // i<j -> sl = j-i, sr=i-j

ss merge(ss l, ss r) {
    if (l.mmin==-1 && r.mmin==-1) return {-1,0,0,0};
    if (l.mmin==-1) return r;
    if (r.mmin==-1) return l;

    ss ans;
    ans.mmax=max(l.mmax,r.mmax);
    ans.mmin=min(l.mmin,r.mmin);
    ans.sl=max({l.sl,r.sl,r.mmax-l.mmin});
    ans.sr=max({l.sr,r.sr,l.mmax-r.mmin});
    return ans;
}

void build_sg(int l, int r, int idx) {
    if (l==r) sg[idx]={h[l],h[l],0,0};
    else {
        int mid=(l+r)/2;
        build_sg(l,mid,2*idx);
        build_sg(mid+1,r,2*idx+1);
        sg[idx]=merge(sg[2*idx],sg[2*idx+1]);
    }
}

ss query_sg(int l, int r, int idx, int x, int y) {
    if (x>r || y<l) return {-1,0,0,0};
    if (x<=l && r<=y) return sg[idx];
    int mid=(l+r)/2;
    return merge(query_sg(l,mid,2*idx,x,y),query_sg(mid+1,r,2*idx+1,x,y));
}

struct node {
    int mmin,mmax,cnt;
    node *l, *r;

    node() : mmin(INT_MAX), mmax(-INT_MAX), cnt(0), l(NULL), r(NULL) {}

    node(int val) : mmin(val), mmax(val), cnt(1), l(NULL), r(NULL) {}

    node(node *L, node *R) : mmin(INT_MAX), mmax(-INT_MAX), cnt(0) , r(R), l(L) {
        if (L) {
            mmin=min(L->mmin,mmin);
            mmax=max(L->mmax,mmax);
            cnt+=L->cnt;
        }

        if (R) {
            mmin=min(R->mmin,mmin);
            mmax=max(R->mmax,mmax);
            cnt+=R->cnt;
        }
    }
};
typedef pair<int,node*> pin;
vector<pin> arr;

struct N {
    int mmin,mmax,cnt;
};

node* build(int l, int r) {
    if (l==r) return new node();
    int mid=(l+r)/2;
    return new node(build(l,mid),build(mid+1,r));
}

node* update(int l, int r, int x, node* pnode) {
    if (x>r || x<l) return pnode;
    if (l==r) return new node(l);
    int mid=(l+r)/2;
    return new node(update(l,mid,x,pnode->l),update(mid+1,r,x,pnode->r));
}

N query(int l, int r, int x, int y, node *pnode) {
    if (x>r || y<l) return {INT_MAX,-INT_MAX,0};
    if (x<=l && r<=y) return {pnode->mmin,pnode->mmax,pnode->cnt};
    int mid=(l+r)/2;
    N ans,L=query(l,mid,x,y,pnode->l),R=query(mid+1,r,x,y,pnode->r);
    ans.mmax=max(L.mmax,R.mmax);
    ans.mmin=min(L.mmin,R.mmin);
    ans.cnt=L.cnt+R.cnt;
    return ans;
}

void build_s(int l, int r, int idx) {
    if (l==r) s[idx]=h[l];
    else {
        int mid=(l+r)/2;
        build_s(l,mid,2*idx);
        build_s(mid+1,r,2*idx+1);
        s[idx]=max(s[2*idx],s[2*idx+1]);
    }
}

int query_s(int l, int r, int idx, int x, int y) {
    if (x>r || y<l) return 0;
    if (x<=l && r<=y) return s[idx];
    int mid=(l+r)/2;
    return max(query_s(l,mid,2*idx,x,y),query_s(mid+1,r,2*idx+1,x,y));
}

void init(int N, vector<int> H) {
    n=N;
    for (int i=0; i<n; ++i) h[i+1]=H[i];

    L[1]=0;
    for (int i=2; i<=n; ++i) {
        int idx=i-1;
        while (h[idx]>=h[i] && idx!=-1) idx=L[idx];
        L[i]=idx;
    }

    R[n]=n+1;
    for (int i=n-1; i>=1; --i) {
        int idx=i+1;
        while (h[idx]>=h[i] && idx!=-1) idx=R[idx];
        R[i]=idx;
    }

    build_s(1,n,1);
    build_sg(1,n,1);

    for (int i=1; i<=n; ++i) {
        int h1=-1,h2=-1;
        if (L[i]+1<=i-1) h1=query_s(1,n,1,L[i]+1,i-1);
        if (i+1<=R[i]-1) h2=query_s(1,n,1,i+1,R[i]-1);

        if (L[i]==0) h1=INT_MAX;
        if (R[i]==n+1) h2=INT_MAX;

        if (h1!=-1 && h2!=-1) v.push_back(pii(min(h1,h2)-h[i],i));
    }

    sort(v.begin(),v.end(),greater<pii>());

    arr.push_back(pin(INT_MAX,build(1,n)));

    for (int i=0; i<v.size(); ++i) {
        node* pnode=update(1,n,v[i].second,arr.back().second);
        if (arr.back().first==v[i].first) arr.pop_back();
        arr.push_back(pin(v[i].first,pnode));
    }
}

int max_towers(int Le, int Ri, int D) {
    ++Le; ++Ri;

    int l=0, r=arr.size()-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        if (arr[mid].first>=D) l=mid;
        else r=mid-1;
    }

    N res=query(1,n,Le,Ri,arr[l].second);
    int cnt=res.cnt,mi=res.mmin,ma=res.mmax;
    assert(cnt>0);
    if (cnt==0) return 1;

    int LL=-1;
    if (mi!=Le && query_s(1,n,1,Le,mi-1)>=h[mi]+D) {
        l=Le; r=mi-1;
        while (l<r) {
            int mid=(l+r+1)/2;
            if (query_s(1,n,1,mid,mi-1)>=h[mi]+D) l=mid;
            else r=mid-1;
        }
        LL=l;
    }
    if (LL!=-1 && query_sg(1,n,1,Le,LL).sl>=D) ++cnt;

    int RR=-1;
    if (ma!=Ri && query_s(1,n,1,ma+1,Ri)>=h[ma]+D) {
        l=ma+1; r=Ri;
        while (l<r) {
            int mid=(l+r)/2;
            if (query_s(1,n,1,ma+1,mid)>=h[ma]+D) r=mid;
            else l=mid+1;
        }
        RR=l;
    }
    if (RR!=-1 && query_sg(1,n,1,RR,Ri).sr>=D) ++cnt;

    return cnt;
}

Compilation message (stderr)

towers.cpp: In constructor 'node::node(node*, node*)':
towers.cpp:45:15: warning: 'node::r' will be initialized after [-Wreorder]
   45 |     node *l, *r;
      |               ^
towers.cpp:45:11: warning:   'node* node::l' [-Wreorder]
   45 |     node *l, *r;
      |           ^
towers.cpp:51:5: warning:   when initialized here [-Wreorder]
   51 |     node(node *L, node *R) : mmin(INT_MAX), mmax(-INT_MAX), cnt(0) , r(R), l(L) {
      |     ^~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int i=0; i<v.size(); ++i) {
      |                   ~^~~~~~~~~

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