Submission #782298

#	Time	Username	Problem	Language	Result	Execution time	Memory
782298		FEDIKUS	Radio Towers (IOI22_towers)	C++17	100 / 100	1198 ms	85460 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int,int>;
using mim = pair<pii,pii>;

const int maxn=1e5+10;
const int logg=18;

int n;
int h[maxn];
multiset<pii > res;
mim sparse[logg][maxn];
int klk;
int dovi[maxn];
int poz[maxn];
pair<int,int> najs[2][logg][maxn];
int staq[maxn];

mim comb(mim &a,mim &b){
  mim ret=a;
  ret.first=max(ret.first,b.first);
  ret.second=min(ret.second,b.second);
  return ret;
}

mim qry(int l,int r){
  mim ret={{h[l],l},{h[l],l}};
  for(int i=logg-1;i>=0;i--){
    if(r-(1<<i)+1>=l){
      ret=comb(ret,sparse[i][r]);
      r-=(1<<i);
    }
  }
  return ret;
}

void resi(int l,int r,multiset<pii > &ret,int naj=2e9+10){
  if(r<l) return;
  najs[0][0][l]=max(najs[0][0][l],{naj,l});
  najs[1][0][r]=max(najs[1][0][r],{naj,r});
  auto temp=qry(l,r);
  pii maxi=temp.first;
  pii mini=temp.second;
  multiset<pii> levi; multiset<pii> desni;
  resi(l,maxi.second-1,levi,maxi.first);
  resi(maxi.second+1,r,desni,maxi.first);
  if(levi.size()>desni.size()) swap(levi,desni);
  for(auto i:desni) levi.emplace(i);
  if(!levi.empty()){
    auto najv=--levi.end();
    int d=naj-mini.first;
    if((*najv).first<d){
        levi.erase(najv);
        levi.emplace(pii(d,mini.second));
    }
  }else{
    levi.emplace(pii(naj-mini.first,mini.second));
  }
  swap(ret,levi);
}

const int siz=4*maxn*logg+10;
int segtsiz=0;
pair<int,pii> segt[siz];
int segtl[siz];
int segtr[siz];

pair<int,pii> combseg(const pair<int,pii> a,const pair<int,pii> b){
	pair<int,pii> ret;
	ret.first=a.first+b.first;
	ret.second.first=max(a.second.first,b.second.first);
	ret.second.second=min(a.second.second,b.second.second);
	return ret;
}

int update(int t,int v,int ind,int l=0,int r=n-1){
  if(l==r){
		segt[segtsiz++]={1,{v,v}};
		return segtsiz-1;
	}
	int mid=l+(r-l)/2;
	int levi=segtl[ind];
	int desni=segtr[ind];
	if(t<=mid) levi=update(t,v,segtl[ind],l,mid);
	else desni=update(t,v,segtr[ind],mid+1,r);
	segt[segtsiz++]=combseg(segt[levi],segt[desni]);
	segtl[segtsiz-1]=levi;
	segtr[segtsiz-1]=desni;
	return segtsiz-1;
}

pair<int,pii> query(int tl,int tr,int ind,int l=0,int r=n-1){
	if(tl<=l && r<=tr) return segt[ind];
	int mid=l+(r-l)/2;
	if(tr<=mid) return query(tl,tr,segtl[ind],l,mid);
	if(tl>mid) return query(tl,tr,segtr[ind],mid+1,r);
	return combseg(query(tl,tr,segtl[ind],l,mid),query(tl,tr,segtr[ind],mid+1,r));
}

int build(int l=0,int r=n-1){
	if(l==r){
		segt[segtsiz++]={0,{-1,INT_MAX}};
		return segtsiz-1;
	}
	int mid=l+(r-l)/2;
	int levi=build(l,mid);
	int desni=build(mid+1,r);
	segt[segtsiz++]=combseg(segt[levi],segt[desni]);
	segtl[segtsiz-1]=levi;
	segtr[segtsiz-1]=desni;
	return segtsiz-1;
}

void init(int _n, vector<int> _h) {
  n=_n;
  for(int i=0;i<n;i++) najs[0][0][i]=najs[1][0][i]={-1,-1};
  for(int i=0;i<n;i++) h[i]=_h[i];

  for(int i=0;i<logg;i++){
    for(int j=0;j<n;j++){
      if(i==0) sparse[i][j]={{h[j],j},{h[j],j}};
      else if(j-(1<<(i-1))>=0) sparse[i][j]=comb(sparse[i-1][j],sparse[i-1][j-(1<<(i-1))]);
      else sparse[i][j]=sparse[i-1][j];
  	}
  }

  resi(0,n-1,res);

  for(int i=1;i<logg;i++){
    for(int j=0;j<n;j++){
      if(j-(1<<(i-1))>=0) najs[0][i][j]=max(najs[0][i-1][j],najs[0][i-1][j-(1<<(i-1))]);
      else najs[0][i][j]=najs[0][i-1][j];

      if(j-(1<<(i-1))>=0) najs[1][i][j]=max(najs[1][i-1][j],najs[1][i-1][j-(1<<(i-1))]);
      else najs[1][i][j]=najs[1][i-1][j];
    }
  }

	klk=0;
  for(auto i:res) {dovi[klk++]=i.first; poz[klk-1]=i.second;}
	staq[klk]=build();
  for(int i=klk-1;i>=0;i--){
		staq[i]=update(poz[i],poz[i],staq[i+1]);
	}
}

pii najupit(int l,int r,int koji){
  pii ret={-1,-1};
  for(int i=logg-1;i>=0;i--){
    if(r-(1<<i)+1>=l){
      ret=max(ret,najs[koji][i][r]);
      r-=(1<<i);
    }
  }
  return ret;
}

int max_towers(int l, int r, int d) {
	if(l==r) return 1;
	int koga=lower_bound(dovi,dovi+klk,d)-dovi;
	auto temp=query(l,r,staq[koga]);
  int ret=temp.first;
	int prvi=temp.second.second;
	int posl=temp.second.first;
	if(prvi==INT_MAX){
		prvi=r+1;
		posl=l-1;
	}

	// za levo
	if(prvi-1>=l){
		auto tmp=najupit(l,prvi-1,1);
		int koji=tmp.second;
		int naj=tmp.first;
		if(qry(l,koji).second.first<=naj-d) ret++;
	}
	// za desno
	if(posl+1<=r){
		auto tmp=najupit(posl+1,r,0);
		int koji=tmp.second;
		int naj=tmp.first;
		if(qry(koji,r).second.first<=naj-d) ret++;
	}
	if(ret==0) ret=1;
  return ret;
}

• 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