#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;
#define dbg(x) cout << "[" << #x << ' ' << x << "] ";
// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//***************** CONSTANTS *****************
const int MXN = 1'00;
const int MXK = 20;
//***************** GLOBAL VARIABLES *****************
int A[MXN], diff[MXN], N;
//***************** AUXILIARY STRUCTS *****************
template<typename T>
struct SparseTable{
int st[MXK][MXN];
int log[MXN];
function<T(const T&,const T&)> merge;
SparseTable(const function<T(const T&, const T&)>& _merge){
merge = _merge;
log[0] = log[1] = 0;
for(int i = 2; i <= N; i++)
log[i] = log[i>>1] + 1;
for(int i = 1; i < N; i++)
st[0][i] = diff[i];
for(int j = 1; j < MXK; j++){
for(int i = 1; i + (1 << j) <= N; i++)
st[j][i] = merge(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}
}
int query(int L, int R){
int j = log[R - L + 1];
return merge(st[j][L], st[j][R - (1 << j) + 1]);
}
};
//***************** MAIN BODY *****************
void solve(){
cin >> N;
for(int i = 1; i <= N; i++){
cin >> A[i];
diff[i-1] = A[i] - A[i-1];
}
SparseTable<int> st([](int a, int b){return min(a, b); });
function<int(const int&)> find = [&](const int& i) -> int {
int lo = i, hi = N - 1, ans = i;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if(st.query(i, mid) >= 0)
ans = mid, lo = mid + 1;
else hi = mid - 1;
}
return ans + 1;
};
// find the min j such that A[j...i] is non decreasing, use a sparse table on a diff array to find minimum j such that min of \
diff is >= 0
// then use pbds to find the number of segments this needs to be broken into
ordered_set<pair<int, int>> s;
// overall approach is nlogn
int ans = 0;
for(int i = 1; i <= N;){
int j = find(i);
int inc = s.order_of_key({A[j], j}) - s.order_of_key({A[i], -1}) + 1;
ans += inc;
// dbg(j) dbg(i) dbg(ans) dbg(inc) dbg(s.order_of_key({A[j], j})) dbg(s.order_of_key({A[i], i})) cout << '\n';
for(; i <= j; i++)
s.insert({A[i], i});
}
cout << ans << '\n';
}
//***************** *****************
int32_t main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
#ifdef LOCAL
auto begin = high_resolution_clock::now();
#endif
int tc = 1;
// cin >> tc;
for (int t = 0; t < tc; t++)
solve();
#ifdef LOCAL
auto end = high_resolution_clock::now();
cout << fixed << setprecision(4);
cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
#endif
return 0;
}
/*
If code gives a WA, check for the following :
1. I/O format
2. Are you clearing all global variables in between tests if multitests are a thing
3. Can you definitively prove the logic
4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/
/*
dp[i] -> minimum no. of subarrays to break into to finish this job
if a subsegment is purely increasing in nature, the number of
3 6 -> 3 3 7
use an ordered set
*/
Compilation message
money.cpp:81:2: warning: multi-line comment [-Wcomment]
81 | // find the min j such that A[j...i] is non decreasing, use a sparse table on a diff array to find minimum j such that min of \
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
