제출 #1190344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190344		imarn	Radio Towers (IOI22_towers)	C++20	17 / 100	355 ms	62460 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){};
};
struct node2{
    int mn,mx,amx;
    node2 operator+(node2 b){
        return {min(mn,b.mn),max(mx,b.mx),max({amx,b.amx,b.mx-mn})};
    }
};
struct node3{
    int mn,mx,amx;
    node3 operator+(node3 b){
        return {min(mn,b.mn),max(mx,b.mx),max({amx,b.amx,mx-b.mn})};
    }
};
const int inf=1e9;
node*rt[4*mxn];
node2 sg2[4*mxn];
node3 sg3[4*mxn];
int t[2*mxn]{0};int n;
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};
void build2(int i,int l,int r){
    if(l==r)return void(sg2[i]={h[l],h[l],0});
    int m=(l+r)>>1;build2(2*i,l,m);build2(2*i+1,m+1,r);
    sg2[i]=sg2[2*i]+sg2[2*i+1];
}
node2 qr2(int i,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return node2{inf,-1,0};
    if(r<=tr&&l>=tl)return sg2[i];
    int m=(l+r)>>1;
    return qr2(2*i,l,m,tl,tr)+qr2(2*i+1,m+1,r,tl,tr);
}
void build3(int i,int l,int r){
    if(l==r)return void(sg3[i]={h[l],h[l],0});
    int m=(l+r)>>1;build3(2*i,l,m);build3(2*i+1,m+1,r);
    sg3[i]=sg3[2*i]+sg3[2*i+1];
}
node3 qr3(int i,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return node3{-1,inf,0};
    if(r<=tr&&l>=tl)return sg3[i];
    int m=(l+r)>>1;
    return qr3(2*i,l,m,tl,tr)+qr3(2*i+1,m+1,r,tl,tr);
}
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;
}
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]);
    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]});
        }
    }build2(1,0,n-1);build3(1,0,n-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);
    if(L==0&&R==n-1)return res;
    if(res==0){
        int l=L,r=R+1;
        while(l<r){
            int md=(l+r)>>1;
            if(qr2(1,0,n-1,L,md).amx>=D)r=md;
            else l=md+1;
        }
        if(l!=R+1){
            res++;
            if(qr3(1,0,n-1,l,R).amx>=D)res++;
        }
        return max(1,res);
    }
    int l=L,r=x;
    while(l<r){
        int md=(l+r)>>1;
        if(qr2(1,0,n-1,L,md).amx>=D)r=md;
        else l=md+1;
    }
    if(qr(l,x,n)-h[x]>=D)res++;
    l=y,r=R;
    while(l<r){
        int md=(l+r+1)>>1;
        if(qr3(1,0,n-1,md,R).amx>=D)l=md;
        else r=md-1;
    }
    if(qr(y+1,l+1,n)-h[y]>=D)res++;
    return res;
}

• 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