Submission #836932

#	Time	Username	Problem	Language	Result	Execution time	Memory
836932		Abrar_Al_Samit	Radio Towers (IOI22_towers)	C++17	0 / 100	4078 ms	7516 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

//subtask 2 & 3

const int nax = 100005;
int n;
bool l_maxima[nax];
int l[nax], r[nax];
int h[nax];
int pmax[nax], nmax[nax];

void init(int N, vector<int> H) {
  n = N;

  for(int i=0; i<n; ++i) h[i] = H[i]; 
}

bool is[nax];
int max_towers(int L, int R, int D) {
	vector<int>H;
	for(int i=L; i<=R; ++i) {
		H.push_back(h[i]);
	}
	n = R-L+1;

	int mn = H[0];
  	for(int i=1; i<n-1; ++i) {
    	if(H[i]>H[i-1] && H[i]>H[i+1]) {
    		l_maxima[i] = 1;
    		l[i] = H[i] - mn;
    		mn = 2e9;
    	} else {
    		mn = min(mn, H[i]);
    	}
  	}


  	int p = -1;
  	for(int i=1; i<n; ++i) if(l_maxima[i]) {
  		pmax[i] = p;
  		p = i;
  	}
  	p = n;
  	for(int i=n-1; i>0; --i) if(l_maxima[i]) {
  		nmax[i] = p;
  		p = i;
  	}

  	mn = H[n-1];
  	for(int i=n-2; i>0; --i) {
  		if(l_maxima[i]) {
  			r[i] = H[i] - mn;
  			mn = 2e9;
  		} else {
  			mn = min(mn, H[i]);
  		}
  	}



	int ret = 1;

	set<pair<int,int>>s;
	for(int i=1; i<n; ++i) if(l_maxima[i]) {
		s.insert({H[i], i});
		is[i] = 1;
	}

	while(!s.empty()) {
		auto [x, i] = *s.begin();
		s.erase(s.begin());
		is[i] = 0;

		if(min(l[i], r[i])>=D) {
			++ret;
			continue;
		}

		int lmin = H[i] - l[i], rmin = H[i] - r[i];

		if(pmax[i]!=-1 && is[pmax[i]]) {
			r[pmax[i]] = max(r[pmax[i]], H[pmax[i]] - rmin);
		}
		if(nmax[i]!=n && is[nmax[i]]) {
			l[nmax[i]] = max(l[nmax[i]], H[nmax[i]] - lmin);
		}
	} 
	return ret;
}

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