#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
const int N = 1e5 + 5;
int n, a[N], s[N][20], lg[N];
int mn(int i, int j) {return a[j] < a[i] ? j : i;}
int get(int l, int r) {
int f = lg[r - l];
return mn(s[l][f], s[r - (1 << f)][f]);
}
int rec(int l = 0, int r = n) {
vector<int> f;
f.push_back(l - 1);
int i = l;
while(i < r) {
int j = get(i, r);
if(len(f) > 1 && a[f.back()] != a[j]) break;
f.push_back(j);
i = j + 1;
}
f.push_back(r);
int ans = !!a[f[1]];
for(int i = 1; i < len(f); ++i)
if(f[i - 1] + 1 < f[i])
ans += rec(f[i - 1] + 1, f[i]);
return ans;
}
void solve() {
for(int i = 0; i < N; ++i)
lg[i] = !i ? 0 : lg[i - 1] +
(1 << lg[i - 1] + 1 <= i);
cin >> n;
for(int i = 0; i < n; ++i)
cin >> a[i], s[i][0] = i;
for(int i = 1; i < 20; ++i)
for(int j = 0; j + (1 << i) <= n; ++j)
s[j][i] = mn(s[j][i - 1],
s[j + (1 << i - 1)][i - 1]);
cout << rec() << endl;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:61:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
61 | (1 << lg[i - 1] + 1 <= i);
| ~~~~~~~~~~^~~
Main.cpp:68:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
68 | s[j + (1 << i - 1)][i - 1]);
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
876 KB |
Output is correct |
| 4 |
Correct |
14 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
23 ms |
6892 KB |
Output is correct |
| 6 |
Correct |
38 ms |
16748 KB |
Output is correct |
| 7 |
Correct |
50 ms |
20716 KB |
Output is correct |
