Submission #149462

#	Time	Username	Problem	Language	Result	Execution time	Memory
149462		USA1 (#200)	Lokahian Relics (FXCUP4_lokahia)	C++17	100 / 100	7 ms	736 KiB

lokahia

#include "lokahia.h"

#include <bits/stdc++.h>
using namespace std;

struct f {
	int first;
	int maxVal = -1;
	int cnt = 1;
};

int FindBase(int N){
	vector<f> ranges;
	for (int i = 0; i < N; ) {
		f cur{i};
		int cnt = 1;
		int j;
		for (j = i+1; cnt > 0 && j < N; j++) {
			int v = CollectRelics(i, j);
			if (v == -1) {
				cnt--;
				ranges.push_back(f{j});
			} else {
				cnt++;
				cur.cnt ++;
				cur.maxVal = max(cur.maxVal, v);
			}
		}

		if (cnt == 0) {
			ranges.push_back(cur);
			i = j;
		} else {
			assert(cnt > 0);
			assert(j == N);
			for (const auto& o : ranges) {
				if (o.first > i) {
					// skip it for speed
					continue;
				}
				int v = CollectRelics(i, o.first);
				if (v == -1) {
					// skip it
				} else {
					cur.cnt += o.cnt;
					cur.maxVal = max(cur.maxVal, o.maxVal);
					cur.maxVal = max(cur.maxVal, v);
				}
			}
			if (cur.cnt > N / 2) {
				if (cur.maxVal == -1) {
					return cur.first;
				} else {
					return cur.maxVal;
				}
			} else {
				return -1;
			}
		}
	}
	return -1;
}

• Subtask 1: 100 / 100