Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define LL long long
- #define N ((int)1e5 + 8)
- #define MAX ((int)1e9 + 8)
- #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
- using namespace std;
- int GetLeft(int n)
- {
- n = FindPar(n);
- return leftIndex[n];
- }
- int GetMax(int n)
- {
- n = FindPar(n);
- return maxH[n];
- }
- void Merge(int a , int b)
- {
- a = FindPar(a) , b = FindPar(b);
- par[a] = b;
- maxH[b] = max(maxH[a] , maxH[b]);
- lefIndex[b] = min(leftIndex[a] , leftIndex[b]);
- }
- int main()
- {
- /// problem: https://lightoj.com/problem/save-the-trees
- /// seg(i) => dp[i-1] + max(i , ... , cur)
- dp[0] = 0;
- for(int i = 1 ; i <= n ; i++){
- leftIndex[i] = i;
- par[i] = i;
- maxH[i] = arr[i];
- }
- leftEnd[1] = 1;
- vis[type[1]] = 1;
- for(int i = 2 ; i <= n ; i++){
- if(vis[type[i]] == 0) leftEnd[i] = leftEnd[i-1];
- else{
- for(int j = leftEnd[i-1] ; j <= i ; j++){
- if(vis[type[i]] == 0){
- leftEnd[i] = j;
- break;
- }
- vis[type[j]] = 0;
- }
- }
- vis[type[i]] = 1;
- }
- for(int cur = 1 ; cur <= n ; cur++){
- for(int i = cur-1 ; i > 0 && GetMax(i) <= arr[cur]; i = GetLeft(i) - 1){
- int from = GetLeft(i);
- Update(from , i , -GetMax(i) + arr[cur]);
- Merge(i , cur);
- }
- Update(cur , cur , arr[cur] + dpp[cur-1]);
- dpp[i] = Query(leftEnd[cur] , cur);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement