| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 626319 | Kaitokid | Radio Towers (IOI22_towers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1000000001;
struct nod;
extern nod*empt;
struct nod{
int val;
nod*l,*r;
nod()
{
l=r=this;
val=0;
}
nod(int x,nod*ll=empt,nod*rr=empt)
{
val=x;
l=ll,r=rr;
}
};
nod*empt=new nod();
nod*insert(nod*rt,int x,int st=0,int en=inf)
{
if(st>x||en<x)return rt;
if(st==en)return new nod(rt->val+1);
int mid=(st+en)>>1;
nod*s1=insert(rt->l,x,st,mid);
nod*s2=insert(rt->r,x,mid+1,en);
return new nod(s1->val+s2->val,s1,s2);
}
int cal(nod*rt1,nod*rt2,int l,int r,int st=0,int en=inf)
{
if(st>r||en<l)return 0;
if(st>=l && en<=r)return rt1->val-rt2->val;
int mid=(st+en)/2;
return cal(rt1->l,rt2->l,l,r,st,mid)+cal(rt1->r,rt2->r,l,r,mid+1,en);
}
nod*prs[100009];
int sg[4][400009];
int frs(int id,int l,int r,int d,int st,int en,int x=0)
{
if(st>r||en<l)return -1;
if(sg[id][x]<d)return -1;
if(st==en)return st;
int mid=(st+en)>>1;
int u=frs(id,l,r,d,st,mid,(x<<1));
if(u!=-1)return u;
return frs(id,l,r,d,mid+1,en,(x<<1)|1);
}
int lst(int id,int l,int r,int d,int st,int en,int x=0)
{
if(st>r||en<l)return -1;
if(sg[id][x]<d)return -1;
if(st==en)return st;
int mid=(st+en)>>1;
int u=lst(id,l,r,d,mid+1,en,(x<<1)|1);
if(u!=-1)return u;
return lst(id,l,r,d,st,mid,(x<<1));
}
int cal(int id,int l,int r,int st,int en,int x=0)
{
if(st>r|| en<l)return 0;
if(st>=l && en<=r)return sg[id][x];
int mid=(st+en)/2;
return max(cal(id,l,r,st,mid,(x<<1)),cal(id,l,r,mid+1,en,(x<<1)|1));
}
void build(int id,vector<int>&v,int st,int en,int x=0)
{
if(st==en){sg[id][x]=v[st];return;}
int mid=(st+en)>>1;
build(id,v,st,mid,(x<<1));
build(id,v,mid+1,en,(x<<1)|1);
sg[id][x]=max(sg[id][(x<<1)],sg[id][(x<<1)|1]);
}
int sz;
void init(int N,vector<int> H)
{
sz=N;
build(0,H,0,N-1);
stack<int>st;
vector<int>g;
for(int i=0;i<N;i++)
{
while((!st.empty())&&(H[st.top()]>H[i]))st.pop();
if(st.empty() ){g.push_back(inf);st.push(i);continue;}
if(st.top()==i-1){g.push_back(0);st.push(i);continue;}int u=cal(0,st.top()+1,i-1,0,N-1);
g.push_back(u-H[i]);
st.push(i);
}
vector<int>f;
while(!st.empty())st.pop();
for(int i=N-1;i>=0;i--)
{
while((!st.empty())&&(H[st.top()]>H[i]))st.pop();
if(st.empty() ){f.push_back(inf);st.push(i);continue;}
if( st.top()==i+1){f.push_back(0);st.push(i);continue;}
int u=cal(0,i+1,st.top()-1,0,N-1);
f.push_back(u-H[i]);
st.push(i);
}
build(1,f,0,N-1);
build(2,g,0,N-1);
prs[0]=empt;
for(int i=0;i<N;i++)
prs[i+1]=insert(prs[i],min(f[i],g[i]));
}
int max_tower(int L,int R,int D)
{
if(L==R)return 1;
if(L==R-1)return 1;
int u=frs(1,L,R,D,0,sz-1);
int v=lst(2,L,R,D,0,sz-1);
if(u==-1 || v==-1 || u>v)return 1;
int ans=2+cal(prs[v],prs[u+1],D,inf);
return ans;
}