fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "map"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 5e5 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int n, a[N], mnL[N], mxL[N], mxR[N], mnR[N];
  39. ll Ans = 0;
  40.  
  41. inline void Read_Input() {
  42.     cin >> n;
  43.     FOR(i, 1, n) {
  44.         int u, v;
  45.         cin >> u >> v;
  46.         a[u] = v;
  47.     }
  48. }
  49.  
  50. void DnC(int L, int R) {
  51.     if (L > R) return;
  52.     if (L == R) {
  53.         Ans++;
  54.         return;
  55.     }
  56.  
  57.     int mid = (L + R) >> 1;
  58.  
  59.     mxL[mid] = a[mid];
  60.     mnL[mid] = a[mid];
  61.     mxR[mid + 1] = a[mid + 1];
  62.     mnR[mid + 1] = a[mid + 1];
  63.  
  64.     FORD(i, mid - 1, L) {
  65.         mxL[i] = max(mxL[i + 1], a[i]);
  66.         mnL[i] = min(mnL[i + 1], a[i]);
  67.     }
  68.  
  69.     FOR(i, mid + 2, R) {
  70.         mxR[i] = max(mxR[i - 1], a[i]);
  71.         mnR[i] = min(mnR[i - 1], a[i]);
  72.     }
  73.  
  74.  
  75.     /// case 1 : mnL + mxL
  76.  
  77.     FORD(i, mid, L) {
  78.         int x = mxL[i] - mnL[i] + i;
  79.         if (x > mid && x <= R &&  mxL[i] > mxR[x] && mnL[i] < mnR[x])
  80.             Ans++;
  81.     }
  82.  
  83.     /// case 2 : mnR + mxR
  84.  
  85.  
  86.     FOR(i, mid + 1, R) {
  87.  
  88.  
  89.         int x = i - mxR[i] + mnR[i];
  90.         if (x <= mid && x >= L && mnR[i] < mnL[x] && mxR[i] > mxL[x])
  91.             Ans++;
  92.  
  93.     }
  94.  
  95.     /// case 3 : mnL + mxR
  96.  
  97.     set< pair<int, int> > S;
  98.     unordered_map<int, int> mp;
  99.  
  100.     for (int i = mid, j = mid + 1; i >= L; i--) {
  101.  
  102.         while (j <= R && mnR[j] >= mnL[i]) {
  103.             S.insert({mxR[j], j});
  104.             mp[mxR[j] - j]++;
  105.             j++;
  106.         }
  107.  
  108.         while (S.size() && (*S.begin()).fi < mxL[i]) {
  109.             int u = (*S.begin()).se;
  110.             S.erase(S.begin());
  111.             mp[mxR[u] - u]--;
  112.         }
  113.  
  114.         int val = mnL[i] - i;
  115.  
  116.         Ans += mp[val];
  117.     }
  118.  
  119.  
  120.     /// case 4 : mxL + mnR
  121.  
  122.     set<pair<int, int>, greater<pair<int, int>> > T;
  123.     mp.clear();
  124.     for (int i = mid, j = mid + 1; i >= L; i--) {
  125.  
  126.         while (j <= R && mxR[j] <= mxL[i]) {
  127.             T.insert({mnR[j], j});
  128.             mp[mnR[j] + j]++;
  129.             j++;
  130.         }
  131.  
  132.         while (T.size() && (*T.begin()).fi > mnL[i]) {
  133.             int u = (*T.begin()).se;
  134.             T.erase(T.begin());
  135.             mp[mnR[u] + u]--;
  136.         }
  137.  
  138.         int val = mxL[i] + i;
  139.  
  140.         Ans += mp[val];
  141.     }
  142.  
  143.  
  144.     DnC(L, mid);
  145.     DnC(mid + 1, R);
  146. }
  147.  
  148. inline void Solve() {
  149.     DnC(1, n);
  150.     cout << Ans;
  151. }
  152.  
  153. Ti20_ntson {
  154.     freopen(TASK".INP","r",stdin);
  155.     freopen(TASK".OUT","w",stdout);
  156.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  157.     int T = 1;
  158. //    cin >> T;
  159.     while (T -- ) {
  160.         Read_Input();
  161.         Solve();
  162.     }
  163. }
  164.  
  165.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/buTngW
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!