oj.uz

Submission #375138

# Submission time Handle Problem Language Result Execution time Memory
375138 2021-03-09T03:34:43 Z dimashii Po (COCI21_po) C++17
20 / 70
 140 ms 28524 KB 
#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]);
}

map <int, vector <int> > pos;

ll solve(int l, int r) {
	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);
		L = pos[x][lb] + 1;
		++lb;
	}if (L <= r && a[r] != x)
		ans += solve(L, r);
	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

Main.cpp: In function 'long long int solve(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
20.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Incorrect 19 ms 4588 KB Output isn't correct
5 Incorrect 24 ms 6764 KB Output isn't correct
6 Correct 107 ms 19948 KB Output is correct
7 Incorrect 140 ms 28524 KB Output isn't correct