Submission #1190320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190320		imarn	Radio Towers (IOI22_towers)	C++20	17 / 100	383 ms	57876 KiB

towers

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<long double>
using namespace std;
const int mxn=1e5+5;
struct node{
    int tt,mn,mx;
    node*l,*r;
    node(int i):tt(1),mn(i),mx(i),l(0),r(0){};
    node():tt(0),mn(2e9),mx(-1),l(0),r(0){};
    node(node*l,node*r):tt(l->tt+r->tt),mn(min(l->mn,r->mn)),mx(max(l->mx,r->mx)),l(l),r(r){};
};
node*rt[4*mxn];
int t[2*mxn]{0};int n,cu=0;pii t2[2*mxn];
int l[mxn],r[mxn],pr[mxn],nx[mxn];
vector<int>h;
vector<int>use;
vector<int>val;
bool ok[mxn]{0},vis[mxn]{0};
node* build(int l,int r){
    if(l==r){
        if(ok[l])return new node(l);
        return new node();
    }int m=(l+r)>>1;
    return new node(build(l,m),build(m+1,r));
}
node *update(node *t,int l,int r,int idx){
    if(l==r){
        return new node();
    }int m=(l+r)>>1;
    if(idx<=m)return new node(update(t->l,l,m,idx),t->r);
    return new node(t->l,update(t->r,m+1,r,idx));
}
t3 que(node *t,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return {0,2e9,-1};
    if(r<=tr&&l>=tl)return make_tuple(t->tt,t->mn,t->mx);
    int m=(l+r)>>1;
    auto [s1,l1,r1]=que(t->l,l,m,tl,tr);
    auto [s2,l2,r2]=que(t->r,m+1,r,tl,tr);
    return make_tuple(s1+s2,min(l1,l2),max(r1,r2));
}
int qr(int l,int r,int sz,int rs=0){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=max(rs,t[l++]);
        if(r&1)rs=max(rs,t[--r]);
    }return rs;
}
pii qr2(int l,int r,int sz,pii rs={-1,-1}){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=max(rs,t2[l++]);
        if(r&1)rs=max(rs,t2[--r]);
    }return rs;
}
void upd2(int i,int sz,int amt){
    i+=sz;t2[i].f=amt;
    for(i>>=1;i;i>>=1)t2[i]=max(t2[2*i],t2[2*i+1]);
}
void init(int N, std::vector<int> H){h=H;
    n=N;for(int i=0;i<N;i++)t[i+n]=H[i];
    for(int i=n-1;i>=1;i--)t[i]=max(t[2*i],t[2*i+1]);
    for(int i=0;i<2*n;i++)t2[i]={-1,-1};
    int pv=-1;
    for(int i=0;i<n;i++){
        bool ch=0;l[i]=2e9,r[i]=2e9;
        pr[i]=i-1;nx[i]=i+1;
        if(i==0&&H[i]<H[i+1])ch=1;
        else if(i==n-1&&H[i]<H[i-1])ch=1;
        else if(i>0&&i<n-1&&H[i]<H[i+1]&&H[i]<H[i-1])ch=1;
        if(ch)ok[i]=1,use.pb(i);
        if(ch&&pv!=-1){
            r[pv]=qr(pv+1,i,n)-H[pv];
            l[i]=qr(pv+1,i,n)-H[i];
        }if(ch)pv=i;
    }priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=0;i<use.size();i++){
        if(i==0)pr[use[i]]=-1;
        else pr[use[i]]=use[i-1];
        if(i==(int)use.size()-1)nx[use[i]]=n;
        else nx[use[i]]=use[i+1];

    }rt[0]=build(0,n-1);val.pb(0);int curr=0,id=0;
    for(int i=0;i<n;i++)if(ok[i])pq.push({min(l[i],r[i]),i});
    while(!pq.empty()){
        auto [d,u]=pq.top();pq.pop();
        if(d<min(l[u],r[u])||vis[u])continue;
        vis[u]=1;
        if(curr!=d+1){
            curr=d+1;val.pb(curr);id++;
            rt[id]=rt[id-1];
        }rt[id]=update(rt[id],0,n-1,u);
        if(pr[u]!=-1)nx[pr[u]]=nx[u];
        if(nx[u]!=n)pr[nx[u]]=pr[u];
        if(pr[u]!=-1&&nx[u]!=n){
            r[pr[u]]=qr(pr[u]+1,nx[u],n)-H[pr[u]];
            l[nx[u]]=qr(pr[u]+1,nx[u],n)-H[nx[u]];
            pq.push({min(r[pr[u]],l[pr[u]]),pr[u]});
            pq.push({min(r[nx[u]],l[nx[u]]),nx[u]});
        }
        else if(pr[u]==-1&&nx[u]!=n){
            l[nx[u]]=2e9;pq.push({min(r[nx[u]],l[nx[u]]),nx[u]});
        }
        else if(pr[u]!=-1&&nx[u]==n){
            r[pr[u]]=2e9;pq.push({min(r[pr[u]],l[pr[u]]),pr[u]});
        }
        t2[u+n]={cu++,u};
    }
    for(int i=n-1;i>0;i--)t2[i]=max(t2[2*i],t2[2*i+1]);
}
int max_towers(int L, int R, int D) {
    if(L==R)return 1;
    auto [res,x,y]=que(rt[ub(val,D)-1],0,n-1,L,R);
    int cnt=0,cnt2=0;
    if(res<=1){
        int tt = qr(L+1,R,n);
        if(tt-h[L]>=D)cnt++;
        if(tt-h[R]>=D)cnt++;
    }
    /*if(res<=1){
        pii xx=qr2(L,R,n);
        if(xx.f!=-1){
            upd2(xx.s,n,-1);
            pii yy = qr2(L,R,n);
            if(yy.f!=-1){
                int tt=qr(xx.s+1,yy.s,n);
                if(tt-h[xx.s]>=D)cnt2++;
                if(tt-h[yy.s]>=D)cnt2++;
            }upd2(xx.s,n,xx.f);
        }
    }*/if(res==0)return max(cnt,cnt2);
    if(L==0&&R==n-1)return res;
    int chl=0,chr=0;int mn=2e9;
    for(int i=L;i<x;i++){
        if(h[i]-mn>=D&&h[i]-h[x]>=D)chl=1;
        mn=min(mn,h[i]);
    }mn=2e9;
    for(int i=R;i>y;i--){
        if(h[i]-mn>=D&&h[i]-h[y]>=D)chr=1;
        mn=min(mn,h[i]);
    }
    return max({res+chl+chr,cnt,cnt2});
}

• 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