제출 #836880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836880		Abrar_Al_Samit	Radio Towers (IOI22_towers)	C++17	0 / 100	4066 ms	4348 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];
  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] - H[i-1];
    	r[i] = H[i] - H[i+1];
    }
  }

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

bool is[nax];
int max_towers(int L, int R, int D) {
	int ret = 1;

	set<pair<int,int>>s;
	for(int i=L+1; i<R; ++i) if(l_maxima[i]) {
		s.insert(make_pair(min(l[i], r[i]), i));
		is[i] = 1;
	}

	while(!s.empty() && s.begin()->first<D) {
		auto [x, i] = *s.begin();
		s.erase(s.begin());
		is[i] = 0;

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

		if(pmax[i]!=-1 && is[pmax[i]]) {
			s.erase(make_pair(min(l[pmax[i]], r[pmax[i]]), pmax[i]));
			r[pmax[i]] = max(r[pmax[i]], h[pmax[i]] - rmin);
			s.insert(make_pair(min(l[pmax[i]], r[pmax[i]]), pmax[i]));
		}
		if(nmax[i]!=n && is[nmax[i]]) {
			s.erase(make_pair(min(l[nmax[i]], r[nmax[i]]), nmax[i]));
			l[nmax[i]] = max(l[nmax[i]], h[nmax[i]] - lmin);
			s.insert(make_pair(min(l[nmax[i]], r[nmax[i]]), nmax[i]));
		}
	} 
	ret = max(ret, (int)s.size() + 1);
	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