General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86273367 Practice:
JKLover
526F - 20 C++17 (GCC 7-32) Accepted 389 ms 21268 KB 2020-07-08 15:23:11 2020-07-08 15:23:11
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int inf = 1e9;
const int N = 3e5 + 10;
struct info
{
	int val, cnt;
	friend info operator + (info A, info B)
	{
		if (A.val == B.val)
			return (info){A.val, A.cnt + B.cnt};
		return A.val < B.val ? A : B;
	}
	void add(int x)
	{
		val += x;
	}
} mi[N << 2];
int tag[N << 2];
void pushup(int x)
{
	mi[x] = mi[x << 1] + mi[x << 1 | 1];
}
void modify(int x, int c)
{
	mi[x].add(c);
	tag[x] += c;
}
void pushdown(int x)
{
	if (tag[x])
	{
		modify(x << 1, tag[x]);
		modify(x << 1 | 1, tag[x]);
		tag[x] = 0;
	}
}
void BuildTree(int x, int l, int r)
{
	if (l == r)
	{
		mi[x].val = l, mi[x].cnt = 1;
		return;		
	}
	int mid = (l + r) >> 1;
	BuildTree(x << 1, l, mid);
	BuildTree(x << 1 | 1, mid + 1, r);
	pushup(x);
}
void upd(int x, int l, int r, int L, int R, int c)
{
	if (L > R)
		return;
	if (L <= l && r <= R)
		return modify(x, c);
	pushdown(x);
	int mid = (l + r) >> 1;
	if (L <= mid)
		upd(x << 1, l, mid, L, R, c);
	if (R > mid)
		upd(x << 1 | 1, mid + 1, r, L, R, c);
	pushup(x);
}
void query(info &res, int x, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
	{
		res = res + mi[x];
		return;
	}
	pushdown(x);
	int mid = (l + r) >> 1;
	if (L <= mid)
		query(res, x << 1, l, mid, L, R);
	if (R > mid)
		query(res, x << 1 | 1, mid + 1, r, L, R);
}
int n, p[N], Mx[N], mxtp = 0, Mi[N], mitp = 0;
int main()
{
	n = read();
	BuildTree(1, 1, n);
	for (int i = 1; i <= n; ++i)
	{
		int x = read(), y = read();
		p[x] = y;
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		while (mxtp && p[Mx[mxtp]] < p[i])
		{
			upd(1, 1, n, Mx[mxtp - 1] + 1, Mx[mxtp], p[i] - p[Mx[mxtp]]);
			--mxtp;
		}
		Mx[++mxtp] = i;
		while (mitp && p[Mi[mitp]] > p[i])
		{
			upd(1, 1, n, Mi[mitp - 1] + 1, Mi[mitp], p[Mi[mitp]] - p[i]);
			--mitp;
		}
		Mi[++mitp] = i;
		info res{inf, 0};
		query(res, 1, 1, n, 1, i);
		if (res.val == i)
			ans += res.cnt;
	}
	cout << ans << '\n';
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details