Submission #375134

#	Time	Username	Problem	Language	Result	Execution time	Memory
375134		dimashii	Sifra (COCI21_sifra)	C++17	0 / 50	1 ms	512 KiB

Main

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int mxN = 1e5 + 5, mod = 1e9 + 7;

int n, a[mxN], lg[mxN];

int st[mxN][18];

void Build() {
	for (int i = 2; i <= n; ++i)
		lg[i] = lg[i / 2] + 1;
	for (int i = 1; i <= n; ++i)
		st[i][0] = a[i];
	for (int j = 1; j < 18; ++j) {
		for (int i = 1; i + (1 << (j - 1)) <= n; ++i)
			st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
	}
}

int Get(int l, int r) {
	int len = r - l + 1;
	int x = lg[len];
	return min(st[l][x], st[r - (1 << x) + 1][x]);
}

unordered_map <int, vector <int> > pos;

ll solve(int l, int r, int del = 0) {
	if (l == r)
		return 1;
	int x = Get(l, r);
	int lb = lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin();
	int L = l;
	ll ans = 1;
	while (lb < pos[x].size() && pos[x][lb] <= r) {
		if (L <= pos[x][lb] - 1) 
			ans += solve(L, pos[x][lb] - 1, x);
		L = pos[x][lb] + 1;
		++lb;
	}if (L <= r && a[r] != x)
		ans += solve(L, r, x);
	return ans;
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i], pos[a[i]].push_back(i);
	Build();
	cout << solve(1, n);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int solve(int, int, int)':
Main.cpp:39:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  while (lb < pos[x].size() && pos[x][lb] <= r) {
      |         ~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 50