Submission #1069752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069752		new_acc	Radio Towers (IOI22_towers)	C++17	100 / 100	1160 ms	73104 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
struct item{
    item *l,*r;
    int sum;
};
const int N=1e5+10;
const int SS=1<<17;
pitem korz[N];
int t[N],n,fau[N],seg[SS*2+10],seg2[SS*2+10],seg3[SS*2+10];
bool wl[N];
pair<int,int> prz[N],org[N];
vector<pair<int,int>> ogl;
void upd2(int a,int b){
    for(a+=SS;a>0;a/=2) seg[a]=max(seg[a],b);
}
void upd3(int a,int b){
    for(a+=SS;a>0;a/=2) seg2[a]=max(seg2[a],b);
}
void upd4(int a,int b){
    for(a+=SS;a>0;a/=2) seg3[a]=max(seg3[a],b);
}
int qr3(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return -1;
    int sr=(p+k)/2;
    if(p>=a and k<=b){
        if(seg2[v]>=x){
            if(p==k) return p;
            if(seg2[v*2]>=x) 
                return qr3(a,b,x,p,sr,v*2);
            else return qr3(a,b,x,sr+1,k,v*2+1);
        }else return -1;
    }
    int val=qr3(a,b,x,p,sr,v*2);
    if(val==-1) return qr3(a,b,x,sr+1,k,v*2+1);
    return val;
}
int qr4(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return -1;
    int sr=(p+k)/2;
    if(p>=a and k<=b){
        if(seg3[v]>=x){
            if(p==k) return p;
            if(seg3[v*2+1]>=x) 
                return qr4(a,b,x,sr+1,k,v*2+1);
            else return qr4(a,b,x,p,sr,v*2);
        }else return -1;
    }
    int val=qr4(a,b,x,sr+1,k,v*2+1);
    if(val==-1) return qr4(a,b,x,p,sr,v*2);
    return val;
}
int qr2(int a,int b){
    int res=0;
    for(a+=SS-1,b+=SS+1;a/2!=b/2;a/=2,b/=2){
        if(a%2==0) res=max(res,seg[a+1]);
        if(b%2) res=max(res,seg[b-1]);
    }
    return res;
}
pitem upd(pitem v,int a,int x,int p=0,int k=SS-1){
    if(p==k){
        pitem xd2=new item;
        xd2->l=nullptr,xd2->r=nullptr,xd2->sum=x+v->sum;
        return xd2;
    }
    int sr=(p+k)/2;
    if(a<=sr){
        pitem xd=upd(v->l,a,x,p,sr);
        pitem xd2=new item;
        xd2->l=xd,xd2->r=v->r,xd2->sum=x+v->sum;
        return xd2;
    }else{
        pitem xd=upd(v->r,a,x,sr+1,k);
        pitem xd2=new item;
        xd2->l=v->l,xd2->r=xd,xd2->sum=x+v->sum;
        return xd2;
    }
}
int qr1(pitem v,int a,int b,int p=0,int k=SS-1){
    if(p>b or k<a) return 0;
    if(p>=a and k<=b) return v->sum;
    int sr=(p+k)/2;
    return qr1(v->l,a,b,p,sr)+qr1(v->r,a,b,sr+1,k);
}
int Find(int a){
    if(fau[a]==a) return a;
    return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
    a=Find(a),b=Find(b);
    prz[b].se=max(prz[b].se,prz[a].se);
    prz[b].fi=min(prz[b].fi,prz[a].fi);
    fau[a]=b;
}
void build(int v,pitem curr){
    curr->sum=0;
    curr->l=nullptr,curr->r=nullptr;
    if(v>=SS) return;
    curr->l=new item,curr->r=new item;
    build(v*2,curr->l),build(v*2+1,curr->r);
}
void init(int nn, std::vector<int> H) {
    n=nn;
    iota(fau,fau+1+n,0);
    for(int i=1;i<=n;i++) t[i]=H[i-1],prz[i]={i,i};
    vector<pair<int,int>> vp;
    for(int i=1;i<=n;i++) vp.push_back({t[i],i});
    sort(vp.begin(),vp.end());
    for(int i=1;i<=n;i++) upd2(i,t[i]);
    for(int i=n-1;i>=0;i--){
        int u=vp[i].se;
        wl[u]=1;
        if(wl[u-1]) Union(u,u-1);
        if(wl[u+1]) Union(u,u+1);
        pair<int,int> pom=prz[Find(u)];
        int praw=qr2(u,pom.se)-t[u],lew=qr2(pom.fi,u)-t[u];
        upd3(u,praw);
        upd4(u,lew);
        ogl.push_back({min(lew,praw),u});
        org[u]=pom;
    }
    sort(ogl.begin(),ogl.end());
    korz[0]=new item;
    build(1,korz[0]);
    for(int i=0;i<(int)ogl.size();i++){
        int u=ogl[i].se;
        korz[i+1]=upd(korz[i],u,1);
    }
}
int max_towers(int l, int r, int d) {
    l++,r++;
    int ind=lower_bound(ogl.begin(),ogl.end(),make_pair(d,0))-ogl.begin();
    int lew=qr3(l,r,d),praw=qr4(l,r,d),res=0;
    pitem k=korz[ind];
    if(lew!=-1){
        if(org[lew].fi<=l and qr1(k,lew,lew)==1) res++;
    }
    if(praw!=-1){
        if(org[praw].se>=r and qr1(k,praw,praw)==1) res++;
    }
    res+=r-l+1-qr1(k,l,r);
    return max(res,1);

}

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