Submission #375165

#	Time	Username	Problem	Language	Result	Execution time	Memory
375165		SeDunion	Po (COCI21_po)	C++17	70 / 70	26 ms	21356 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;
 
const int LOG = 20;
 
pair<int,int> sp[LOG][N];
 
int lg[N];
 
pair<int,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, int h = 0) {
	if (l >= r) return 0;
	auto [val, i] = mn(l, r);
	return solve(l, i, val) + solve(i + 1, r, val) + (val != h);
}
 
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].first; sp[0][i].second = 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: 70 / 70