Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

|

General

# Author Problem Lang Verdict Time Memory Sent Judged
86273367 Practice:
JKLover
526F - 20 GNU C++17 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;
{
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;
}
{
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)
{
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()
{
BuildTree(1, 1, n);
for (int i = 1; i <= n; ++i)
{
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
?
?
?
?