Submission #966849

#	Time	Username	Problem	Language	Result	Execution time	Memory
966849		42kangaroo	Radio Towers (IOI22_towers)	C++17	56 / 100	689 ms	12392 KiB

towers

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

#include <utility>
#include <vector>

std::vector<int> a;

std::vector<std::vector<int>> binT;
std::vector<int> sufMin;
std::vector<int> preMin;

int maxI = 0;

void init(int N, std::vector<int> H) {
	using namespace std;
	a = std::move(H);
	binT.clear();
	sufMin.clear();
	preMin.clear();
}

void binJ(std::vector<int> st) {
	using namespace std;
	binT = vector<vector<int>>(20, vector<int>(st.size() + 1));
	for (int i = 0; i < st.size(); ++i) {
		binT[0][i] = st[i];
	}
	binT[0].back() = st.size();
	for (int i = 1; i < 20; ++i) {
		for (int j = 0; j < st.size() + 1; ++j) {
			binT[i][j] = binT[i - 1][binT[i - 1][j]];
		}
	}
}

int max_towers(int L, int R, int D) {
	using namespace std;
    if (binT.empty()) {
		vector<pair<int,int>> rang(a.size());
		vector<int> st;
	    for (int i = 0; i < a.size(); ++i) {
			while (!st.empty() && a[i] >= a[st.back()]) st.pop_back();
			auto ne = lower_bound(st.rbegin(), st.rend(), a[i] + D, [&](int l, int r){return a[l] < r;});
			if (ne == st.rend()) {
				rang[i].first = -1;
			} else rang[i].first = *ne;
			st.push_back(i);
	    }
		st.clear();
		for (int i = a.size() - 1; i >=0; --i) {
		    while (!st.empty() && a[i] >= a[st.back()]) st.pop_back();
		    auto ne = lower_bound(st.rbegin(), st.rend(), a[i] + D, [&](int l, int r){return a[l] < r;});
		    if (ne == st.rend()) {
			    rang[i].second = a.size();
		    } else rang[i].second = *ne;
		    st.push_back(i);
	    }
		sufMin.resize(a.size() + 1);
		sufMin.back() = 1e9;
	    for (int i = a.size() - 1; i >= 0; --i) {
		    sufMin[i] = min(sufMin[i + 1], rang[i].second);
	    }
	    preMin.resize(a.size() + 1);
	    preMin.front() = -1;
	    for (int i =0; i < a.size(); ++i) {
			preMin[i + 1] = max(preMin[i], rang[i].first);
	    }
		vector<int> evs(a.size(), a.size());
	    for (int i = a.size() - 1; i >= 0; --i) {
		    if (rang[i].first >= 0) evs[rang[i].first] = min(evs[rang[i].first], rang[i].second);
			if (i < a.size() - 1) evs[i] = min(evs[i], evs[i + 1]);
	    }
		binJ(evs);
	}
	int ans = 2;
	L = sufMin[L];
	R = preMin[R + 1];
	if (R < L) return 1;
	for (int i = 19; i >= 0; --i) {
		if (binT[i][L] <= R) {
			L = binT[i][L];
			ans += 1 << i;
		}
	}
	return ans;
}

Compilation message (stderr)

towers.cpp: In function 'void binJ(std::vector<int>)':
towers.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < st.size(); ++i) {
      |                  ~~^~~~~~~~~~~
towers.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int j = 0; j < st.size() + 1; ++j) {
      |                   ~~^~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |      for (int i = 0; i < a.size(); ++i) {
      |                      ~~^~~~~~~~~~
towers.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |      for (int i =0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
towers.cpp:72:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    if (i < a.size() - 1) evs[i] = min(evs[i], evs[i + 1]);
      |        ~~^~~~~~~~~~~~~~

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