제출 #375142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375142		SeDunion	Po (COCI21_po)	C++17	10 / 70	67 ms	56044 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

const int LOG = 20;

int sp[LOG][N];

int lg[N];

vector<int>pos[N];

int mn(int l, int r) {
	int j = lg[r - l];
	return min(sp[j][l], sp[j][r - (1 << j)]);
}

int solve(int l, int r) {
	if (l >= r) return 0;
	auto val = mn(l, r);
	auto it = lower_bound(pos[val].begin(), pos[val].end(), l);
	int res = 1;
	res += solve(l, *it - 1);
	while (next(it) != pos[val].end() && *next(it) < r) {
		res += solve(*it + 1, *next(it) - 1);
		it++;
	}
	res += solve(*it + 1, r);
	//cout << l << " " << r << " " << res << endl;
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	lg[1] = 0; for (int i = 2 ; i < N ; ++ i) lg[i] = lg[i>>1] + 1;
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; ++ i) {
		cin >> sp[0][i];
		pos[sp[0][i]].emplace_back(i);
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i + (1 << j) <= n ; ++ i) {
			sp[j][i] = min(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
		}
	}
	cout << solve(0, n);
}

• Subtask 1: 10 / 70