Submission #782286

#	Time	Username	Problem	Language	Result	Execution time	Memory
782286		FEDIKUS	Radio Towers (IOI22_towers)	C++17	14 / 100	959 ms	85564 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 uniq[maxn];
pair<int,int> najs[2][logg][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);
}

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];
    }
  }
}

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 D=-1;

pair<int,pii> segt[4*maxn+10];

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;
}

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

pair<int,pii> query(int tl,int tr,int ind=1,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,2*ind,l,mid);
	if(tl>mid) return query(tl,tr,2*ind+1,mid+1,r);
	return combseg(query(tl,tr,2*ind,l,mid),query(tl,tr,2*ind+1,mid+1,r));
}

int max_towers(int l, int r, int d) {
  if(D==-1){
			for(int i=0;i<4*maxn+10;i++) segt[i]={0,{-1,INT_MAX}};
      for(auto i:res){
          if(i.first>=d) update(i.second,i.second);
      }
      D=d;
  }
	if(l==r) return 1;
	if(r==l+1) return 1;
	auto temp=query(l,r);
  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++;
	}
  return ret;
}
/*
7 1
1 10 4 11 15 12 3  
3 5 1
*/

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