Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*#pragma comment(linker, "/stack:200000000")
- #pragma GCC optimize("O3")
- #pragma GCC target ("avx2")
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")*/
- #include<bits/stdc++.h>
- #define sz(v) (int)v.size()
- #define ll long long
- #define pb push_back
- #define x first
- #define y second
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define nl "\n"
- using namespace std;
- using pii = pair<int, int>;
- const int N = (int)3e5 + 7; // make sure this is right
- const int M = (int)15e6 + 7;
- const int inf = (int)1e9 + 7;
- const ll INF = (ll)3e18 + 7;
- const ll MOD = (ll)998244353; // make sure this is right
- pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
- int n, a[N], mx1[N], mx2[N], mn1[N], mn2[N];
- vector<int> pos[3 * N];
- int get(int i, int x) {
- int l = 1, r = sz(pos[x]), res = 0;
- while(l <= r) {
- int mid = (l + r) >> 1;
- if(pos[x][mid - 1] <= i) {
- res = mid;
- l = mid + 1;
- } else
- r = mid - 1;
- }
- return res;
- }
- int get(int l, int r, int x) {
- if(l > r) return 0;
- return max(0, get(r, x + n) - get(l - 1, x + n));
- }
- ll f(int l, int r) {
- if(l == r) return 1;
- int mid = (l + r) >> 1;
- ll res = f(l, mid) + f(mid + 1, r);
- mx1[mid] = mx2[mid + 1] = -inf;
- mn1[mid] = mn2[mid + 1] = inf;
- for(int i = mid + 1; i <= r; ++i) {
- mx1[i] = max(mx1[i - 1], a[i]);
- mn1[i] = min(mn1[i - 1], a[i]);
- }
- for(int i = mid; i >= l; --i) {
- mn2[i] = min(mn2[i + 1], a[i]);
- mx2[i] = max(mx2[i + 1], a[i]);
- }
- int j = mid + 1;
- map<int, int> cnt;
- for(int i = mid + 1; i <= r; ++i) {
- while(j > l && mx2[j - 1] <= mx1[i] && mn2[j - 1] >= mn1[j]) {
- j--;
- cnt[j]++;
- }
- if(i - mx1[i] + mn1[i] >= l && i - mx1[i] + mn1[i] <= mid) res += cnt[i - mx1[i] + mn1[i]];
- }
- cnt.clear();
- j = mid;
- for(int i = mid; i >= l; --i) {
- while(j < r && mx1[j + 1] <= mx2[i] && mn1[j + 1] >= mn2[i]) {
- j++;
- cnt[j]++;
- }
- if(mx2[i] - mn2[i] + i >= mid + 1 && mx2[i] - mn2[i] + i <= r) res += cnt[mx2[i] - mn2[i] + i];
- }
- for(int i = l; i <= mid; ++i) {
- pos[i - mn2[i] + n].pb(i);
- }
- int L = mid, R = mid + 1;
- for(int i = mid + 1; i <= r; ++i) {
- while(L >= l && mn2[L] > mn1[i]) {
- L--;
- }
- while(R > l && mx2[R - 1] <= mx1[i]) {
- R--;
- }
- res += get(R, L, i - mx1[i]);
- }
- for(int i = l; i <= mid; ++i) {
- pos[i - mn2[i] + n].clear();
- }
- for(int i = mid + 1; i <= r; ++i) {
- pos[i + mn1[i] + n].pb(i);
- }
- R = mid;
- L = mid + 1;
- for(int i = mid; i >= l; --i) {
- while(R < r && mx1[R + 1] <= mx2[i]) {
- R++;
- }
- while(L <= r && mn1[L] > mn2[i]) {
- L++;
- }
- res += get(L, R, i + mx2[i]);
- }
- for(int i = mid + 1; i <= r; ++i) {
- pos[i + mn1[i] + n].clear();
- }
- return res;
- }
- void solve() {
- cin >> n;
- for(int i = 1; i <= n; ++i) {
- int x, y;
- cin >> x >> y;
- a[x] = y;
- }
- cout << f(1, n) << nl;
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int test = 1;
- //cin >> test;
- for(int i = 1; i <= test; ++i) {
- //cout << "Case #" << i << ": ";
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement