/***************************************************************************/
/********************** LANG TU HAO HOA **********************************/
/***************************************************************************/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define sz(x) ((int) x.size())
#define PB push_back
#define PF push_front
#define MP make_pair
#define ll long long
#define F first
#define S second
#define maxc 1000000007
#define MOD 1000000007
#define base 107
#define eps 1e-6
#define pi acos(-1)
#define N 100005
#define task "grow"
#define remain(x) ((x > MOD) ? (x - MOD) : x)
using namespace std;
int n, m, h[N];
vector <int> luu, v;
void Sub1()
{
FOR(i, 1, m)
{
char c;
int x, y;
cin >> c >> x >> y;
if (c == 'F')
{
int pos = lower_bound(h+1, h+n+1, y) - h;
x = min(x, n-pos+1);
int val = h[pos+x-1];
int l = lower_bound(h+pos, h+n+1, val) - h;
int r = upper_bound(h+pos, h+n+1, val) - h - 1;
FOR(i, pos, l-1) h[i]++;
x -= (l - pos);
FORD(i, r, r-x+1) h[i]++;
}
else cout << upper_bound(h+1, h+n+1, y) - lower_bound(h+1, h+n+1, x) << '\n';
}
}
struct IT
{
pii t[N << 2];
int lazy[N<<2];
void Build (int l, int r, int id)
{
if (l == r)
{
t[id] = MP(h[l], h[l]);
return;
}
int mid = (l + r) >> 1;
Build(l, mid, id*2);
Build(mid+1, r, id*2+1);
t[id].F = max(t[id*2].F, t[id*2+1].F);
t[id].S = min(t[id*2].S, t[id*2+1].S);
}
void Push(int l, int r, int id)
{
if (!lazy[id]) return;
t[id].F += lazy[id];
t[id].S += lazy[id];
if (l == r) {lazy[id] = 0; return;}
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id] = 0;
}
void Upd(int l, int r, int id, int u, int v)
{
if (l > v || r < u) return;
if (l >= u && r <= v)
{
lazy[id]++;
Push(l, r, id);
return;
}
Push(l, r, id);
int mid = (l + r) >> 1;
Upd(l, mid, id*2, u, v);
Upd(mid+1, r, id*2+1, u, v);
t[id].F = max(t[id*2].F, t[id*2+1].F);
t[id].S = min(t[id*2].S, t[id*2+1].S);
}
pii Get(int l, int r, int id, int u, int v)
{
if (l > v || r < u) return MP(-maxc, maxc);
if (l >= u && r <= v)
{
Push(l, r, id);
return t[id];
}
Push(l, r, id);
int mid = (l + r) >> 1;
pii m1 = Get(l, mid, id*2, u, v);
pii m2 = Get(mid+1, r, id*2+1, u, v);
return MP(max(m1.F, m2.F), min(m1.S, m2.S));
}
int Find_max(int l, int r, int id, int val)
{
if (l == r)
{
Push(l, r, id);
if (t[id].F <= val) return l;
return -1;
}
Push(l, r, id);
int mid = (l + r) >> 1;
int cur = Get(1, n, 1, mid+1, n).S;
if (cur <= val) return Find_max(mid+1, r, id*2+1, val);
return Find_max(l, mid, id*2, val);
}
int Find_min(int l, int r, int id, int val)
{
if (l == r)
{
Push(l, r, id);
if (t[id].S >= val) return l;
return -1;
}
Push(l, r, id);
int mid = (l + r) >> 1;
int cur = Get(1, n, 1, 1, mid).F;
if (cur < val) return Find_min(mid+1, r, id*2+1, val);
return Find_min(l, mid, id*2, val);
}
} Tree;
void Full()
{
Tree.Build(1, n, 1);
FOR(i, 1, m)
{
char c;
int x, y;
cin >> c >> x >> y;
if (c == 'F')
{
int pos = Tree.Find_min(1, n, 1, y);
if (pos == -1) continue;
x = min(x, n-pos+1);
int val = Tree.Get(1, n, 1, pos, pos+x-1).F;
int l = Tree.Find_min(1, n, 1, val);
int r = Tree.Find_max(1, n, 1, val);
if (pos <= l-1) Tree.Upd(1, n, 1, pos, l-1);
x -= (l - pos);
Tree.Upd(1, n, 1, r-x+1, r);
}
else
{
int l = Tree.Find_min(1, n, 1, x);
int r = Tree.Find_max(1, n, 1, y);
if (l == -1 || r == -1)
{
cout << "0\n";
continue;
}
cout << (r - l + 1) << '\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
//freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
cin >> n >> m;
FOR(i, 1, n) cin >> h[i];
sort(h+1, h+n+1);
//Sub1();
Full();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
3788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
5004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
4920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
377 ms |
4944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
232 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
339 ms |
5476 KB |
Output isn't correct |
