Submission #932353

#	Time	Username	Problem	Language	Result	Execution time	Memory
932353		winter0101	Radio Towers (IOI22_towers)	C++17	100 / 100	2285 ms	488660 KiB

towers

#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
int a[maxn],prv[maxn],nxt[maxn],mx1[maxn],mx2[maxn];
int st_max[maxn<<2];
void buildd(int id,int l,int r){
if (l==r){
st_max[id]=a[l];
return;
}
int mid=(l+r)>>1;
buildd(id<<1,l,mid);
buildd(id<<1|1,mid+1,r);
st_max[id]=max(st_max[id<<1],st_max[id<<1|1]);
}
int get_max(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st_max[id];
int mid=(l+r)>>1;
return max(get_max(id<<1,l,mid,u,v),get_max(id<<1|1,mid+1,r,u,v));
}
int n;
void build_pre(){
stack<int>t;
t.push(0);
for1(i,1,n){
while (!t.empty()&&a[t.top()]>a[i])t.pop();
prv[i]=t.top();
t.push(i);
mx1[i]=get_max(1,1,n,prv[i]+1,i-1)-a[i];
}
}
void build_suf(){
stack<int>t;
t.push(n+1);
for2(i,n,1){
while (!t.empty()&&a[t.top()]>a[i])t.pop();
nxt[i]=t.top();
t.push(i);
mx2[i]=get_max(1,1,n,i+1,nxt[i]-1)-a[i];
}
}
struct node{
vector<int>t;
int val,l,r;
node(){
t.clear();
val=l=r=0;
}
}st[10000009];
int lx[10000009],rx[10000009];
node cmp(const node &np, const node &nq,int d){
if (np.l==0)return nq;
if (nq.l==0)return np;
node p=np,q=nq,r;
r.val=p.val+q.val;
r.l=p.l,r.r=q.r;
while (!p.t.empty()){
auto u=p.t.back();
if (nxt[u]<=q.r&&nxt[u]>=q.l&&mx2[u]<d){
p.t.pop_back();
r.val--;
}
else break;
}
vector<int>tmp;
for (auto v:p.t){
tmp.pb(v);
}
for (auto v:q.t){
if (prv[v]>=p.l&&p.r>=prv[v]&&mx1[v]<d){
r.val--;
continue;
}
tmp.pb(v);
}
if (sz(tmp)==1){
r.t.pb(tmp[0]);
}
else if (sz(tmp)>=2){
r.t.pb(tmp[0]),r.t.pb(tmp.back());
}
return r;
}
int nnode=0;
int copy(int id){
nnode++;
lx[nnode]=lx[id];
rx[nnode]=rx[id];
return nnode;
}
int build(int id,int l,int r,int d){
st[id]=node();
st[id].l=l,st[id].r=r;
if (l==r){
st[id].val=1;
st[id].t.pb(l);
return id;
}
int mid=(l+r)>>1;
lx[id]=build(id<<1,l,mid,d);
rx[id]=build(id<<1|1,mid+1,r,d);
st[id]=cmp(st[id<<1],st[id<<1|1],d);
return id;
}
int update(int id,int l,int r,int u,int d){
if (l>u||r<u)return id;
if (l==r){
int newnode=copy(id);
st[newnode].val=1;
st[newnode].t.pb(l);
st[newnode].l=st[newnode].r=l;
return newnode;
}
int mid=(l+r)>>1;
int newnode=copy(id);
lx[newnode]=update(lx[id],l,mid,u,d);
rx[newnode]=update(rx[id],mid+1,r,u,d);
st[newnode]=cmp(st[lx[newnode]],st[rx[newnode]],d);
return newnode;
}
node get(int id,int l,int r,int u,int v,int d){
if (l>v||r<u||u>v)return node();
if (u<=l&&r<=v)return st[id];
int mid=(l+r)>>1;
return cmp(get(lx[id],l,mid,u,v,d),get(rx[id],mid+1,r,u,v,d),d);
}
vector<int>reup[maxn*2];
vector<int>value;
int root[maxn*2];
void init(int N, std::vector<int> H) {
n=N;
for1(i,1,n)a[i]=H[i-1];
buildd(1,1,n);
build_pre(),build_suf();
build(1,1,n,0);
value.pb(0);
for1(i,1,n){
mx1[i]=max(mx1[i],0),mx2[i]=max(mx2[i],0);
value.pb(mx1[i]),value.pb(mx2[i]);
}
sort(all(value));
value.resize(distance(value.begin(),unique(all(value))));
for1(i,1,n){
reup[lower_bound(all(value),mx1[i])-value.begin()].pb(i);
reup[lower_bound(all(value),mx2[i])-value.begin()].pb(i);
}
nnode=4*n;
root[0]=1;
for1(i,1,sz(value)-1){
root[i]=root[i-1];
for (auto v:reup[i]){
root[i]=update(root[i],1,n,v,value[i]+1);
}
}
}
int max_towers(int L, int R, int D) {
L++,R++;
int l=0,r=sz(value)-1,ans=0;
while (l<=r){
int mid=(l+r)>>1;
if (value[mid]<D){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
node tmp=get(root[ans],1,n,L,R,D);
return tmp.val;
}

• 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