제출 #375164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375164		SeDunion	Po (COCI21_po)	C++17	50 / 70	58 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);
	int it = lower_bound(pos[val].begin(), pos[val].end(), l) - pos[val].begin();
	int res = val != 0;
	res += solve(l, pos[val][it]);
	while (it + 1 < (int)pos[val].size() &&	pos[val][it + 1] < r) {
		res += solve(pos[val][it] + 1, pos[val][it + 1]);
		it++;
	}
	res += solve(pos[val][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: 50 / 70