Advertisement
Guest User

Untitled

a guest
Oct 29th, 2022
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1. /*#pragma comment(linker, "/stack:200000000")
  2. #pragma GCC optimize("O3")
  3. #pragma GCC target ("avx2")
  4. #pragma GCC optimize("Ofast")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #pragma GCC optimize("unroll-loops")*/
  7.  
  8. #include<bits/stdc++.h>
  9.  
  10. #define sz(v) (int)v.size()
  11. #define ll long long
  12. #define pb push_back
  13. #define x first
  14. #define y second
  15. #define all(v) v.begin(), v.end()
  16. #define rall(v) v.rbegin(), v.rend()
  17. #define nl "\n"
  18.  
  19. using namespace std;
  20. using pii = pair<int, int>;
  21.  
  22. const int N = (int)3e5 + 7; // make sure this is right
  23. const int M = (int)15e6 + 7;
  24. const int inf = (int)1e9 + 7;
  25. const ll INF = (ll)3e18 + 7;
  26. const ll MOD = (ll)998244353; // make sure this is right
  27.  
  28. pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  29.  
  30. int n, a[N], mx1[N], mx2[N], mn1[N], mn2[N];
  31. vector<int> pos[3 * N];
  32.  
  33. int get(int i, int x) {
  34.     int l = 1, r = sz(pos[x]), res = 0;
  35.     while(l <= r) {
  36.         int mid = (l + r) >> 1;
  37.         if(pos[x][mid - 1] <= i) {
  38.             res = mid;
  39.             l = mid + 1;
  40.         } else
  41.             r = mid - 1;
  42.     }
  43.     return res;
  44. }
  45.  
  46. int get(int l, int r, int x) {
  47.     if(l > r) return 0;
  48.     return max(0, get(r, x + n) - get(l - 1, x + n));
  49. }
  50.  
  51. ll f(int l, int r) {
  52.     if(l == r) return 1;
  53.  
  54.     int mid = (l + r) >> 1;
  55.     ll res = f(l, mid) + f(mid + 1, r);
  56.     mx1[mid] = mx2[mid + 1] = -inf;
  57.     mn1[mid] = mn2[mid + 1] = inf;
  58.     for(int i = mid + 1; i <= r; ++i) {
  59.         mx1[i] = max(mx1[i - 1], a[i]);
  60.         mn1[i] = min(mn1[i - 1], a[i]);
  61.     }  
  62.     for(int i = mid; i >= l; --i) {
  63.         mn2[i] = min(mn2[i + 1], a[i]);
  64.         mx2[i] = max(mx2[i + 1], a[i]);
  65.     }
  66.     int j = mid + 1;
  67.     map<int, int> cnt;
  68.     for(int i = mid + 1; i <= r; ++i) {
  69.         while(j > l && mx2[j - 1] <= mx1[i] && mn2[j - 1] >= mn1[j]) {
  70.             j--;  
  71.             cnt[j]++;
  72.         }                
  73.         if(i - mx1[i] + mn1[i] >= l && i - mx1[i] + mn1[i] <= mid) res += cnt[i - mx1[i] + mn1[i]];
  74.     }
  75.     cnt.clear();
  76.     j = mid;
  77.     for(int i = mid; i >= l; --i) {
  78.         while(j < r && mx1[j + 1] <= mx2[i] && mn1[j + 1] >= mn2[i]) {
  79.             j++;
  80.             cnt[j]++;
  81.         }  
  82.         if(mx2[i] - mn2[i] + i >= mid + 1 && mx2[i] - mn2[i] + i <= r) res += cnt[mx2[i] - mn2[i] + i];
  83.     }
  84.  
  85.     for(int i = l; i <= mid; ++i) {
  86.         pos[i - mn2[i] + n].pb(i);
  87.     }
  88.     int L = mid, R = mid + 1;        
  89.     for(int i = mid + 1; i <= r; ++i) {
  90.         while(L >= l && mn2[L] > mn1[i]) {
  91.             L--;
  92.         }          
  93.         while(R > l && mx2[R - 1] <= mx1[i]) {
  94.             R--;
  95.         }
  96.         res += get(R, L, i - mx1[i]);
  97.     }
  98.     for(int i = l; i <= mid; ++i) {
  99.         pos[i - mn2[i] + n].clear();
  100.     }
  101.     for(int i = mid + 1; i <= r; ++i) {
  102.         pos[i + mn1[i] + n].pb(i);
  103.     }
  104.     R = mid;
  105.     L = mid + 1;
  106.     for(int i = mid; i >= l; --i) {
  107.         while(R < r && mx1[R + 1] <= mx2[i]) {
  108.             R++;
  109.         }
  110.         while(L <= r && mn1[L] > mn2[i]) {
  111.             L++;
  112.         }
  113.         res += get(L, R, i + mx2[i]);
  114.     }
  115.    
  116.     for(int i = mid + 1; i <= r; ++i) {
  117.         pos[i + mn1[i] + n].clear();
  118.     }
  119.  
  120.     return res;
  121. }
  122.  
  123. void solve() {
  124.     cin >> n;
  125.     for(int i = 1; i <= n; ++i) {
  126.         int x, y;
  127.         cin >> x >> y;
  128.         a[x] = y;
  129.     }
  130.     cout << f(1, n) << nl;
  131. }                                                  
  132.  
  133. signed main() {
  134.     ios_base::sync_with_stdio(0);
  135.     cin.tie(0);
  136.     int test = 1;
  137.     //cin >> test;
  138.     for(int i = 1; i <= test; ++i) {
  139.         //cout << "Case #" << i << ": ";
  140.         solve();
  141.     }
  142.     return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement