#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
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) {
| ~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
