Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 5e5 + 10;
- const int MAXK = 25;
- array<array<int, MAXK>, MAXN> dp;
- array<int, MAXN> prevMin, nextMin, prevMax, nextMax;
- map<int, int> lastOccur;
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N; cin >> N;
- vector<int> v(N+2);
- for (int i = 1; i <= N; i++)
- cin >> v[i];
- for (int i = 1; i < N; i++)
- dp[i][0] = min(v[i], v[i+1]);
- for (int k = 1; k < MAXK; k++)
- for (int i = 1; i <= N; i++)
- dp[i][k] = min(dp[i][k-1], dp[i + (1 << (k-1))][k-1]);
- stack<int> Max, Min;
- for (int i = 1; i <= N; i++)
- {
- while (!Max.empty() && v[Max.top()] < v[i]) Max.pop();
- while (!Min.empty() && v[Min.top()] > v[i]) Min.pop();
- prevMin[i] = (Min.empty() ? 0 : Min.top()); prevMax[i] = (Max.empty() ? 0 : Max.top());
- Min.push(i); Max.push(i);
- }
- while (!Max.empty()) Max.pop();
- while (!Min.empty()) Min.pop();
- for (int i = N; i >= 1; i--)
- {
- while (!Max.empty() && v[Max.top()] < v[i]) Max.pop();
- while (!Min.empty() && v[Min.top()] > v[i]) Min.pop();
- nextMin[i] = (Min.empty() ? N+1 : Min.top()); nextMax[i] = (Max.empty() ? N+1 : Max.top());
- Min.push(i); Max.push(i);
- }
- int resp = 2;
- for (int i = 1; i <= N; i++)
- {
- int l = prevMax[i]+1, r = nextMax[i]-1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
