#include<bits/stdc++.h>
using namespace std;
struct segtree
{
struct node
{
int max;
int lazy = 0;
node(int v) : max(v)
{
}
node() : max(-1)
{
}
};
void merge(node &c, node a, node b)
{
c.max = max(a.max, b.max);
}
int n;
int w;
vector < node > T;
segtree(vector < int > V)
{
w = V.size();
for (n = 1; n < V.size(); n *= 2);
T.resize(n*2);
for (int i = 0; i < V.size(); i++)
T[n+i] = node(V[i]);
for (int k = n-1; k; k--)
merge(T[k], T[k*2], T[k*2+1]);
}
void propagate(int k)
{
T[k].max += T[k].lazy;
if (k < n)
{
T[k*2].lazy += T[k].lazy;
T[k*2+1].lazy += T[k].lazy;
}
T[k].lazy = 0;
}
void add(int l, int r, int k=1, int x=0, int y=-1)
{
if (y == -1)
y = n;
if (l <= x && y <= r)
T[k].lazy++;
propagate(k);
if (l <= x && y <= r)
return;
if (r <= x || y <= l)
return;
int m = (x+y)/2;
add(l, r, k*2, x, m);
add(l, r, k*2+1, m, y);
merge(T[k], T[k*2], T[k*2+1]);
}
int right_bound(int l, int r, int h, int k=1, int x=0, int y=-1)
{
if (y == -1)
y = n;
propagate(k);
if (r <= x || y <= l)
return w;
if (T[k].max < h)
return w;
if (x == y-1)
return x;
int m = (x+y)/2;
int ans = right_bound(l, r, h, k*2, x, m);
if (ans == w)
ans = right_bound(l, r, h, k*2+1, m, y);
return ans;
}
};
int main()
{
int N, M;
cin >> N >> M;
vector < int > H(N);
for (int &h : H)
cin >> h;
sort(H.begin(), H.end());
segtree seg(H);
for (int m = 0; m < M; m++)
{
char t;
cin >> t;
if (t == 'F')
{
int c, h;
cin>> c >> h;
int i = seg.right_bound(0, N, h);
int l = h, r = (M+N)+1;
while(l < r-1)
{
int m = (l+r)/2;
int j = seg.right_bound(i, N, m);
if ((j-i) <= c)
l = m;
else
r = m;
}
int j1 = seg.right_bound(i, N, l);
int j2 = seg.right_bound(i, N, r);
int leftover = c - (j1 - i);
seg.add(i, j1);
seg.add(j2-leftover, j2);
}
else
{
int mi, ma;
cin >> mi >> ma;
int i = seg.right_bound(0, N, mi);
int j = seg.right_bound(0, N, ma+1);
cout << j-i << "\n";
}
}
}
Compilation message
grow.cpp: In constructor 'segtree::segtree(std::vector<int>)':
grow.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (n = 1; n < V.size(); n *= 2);
| ~~^~~~~~~~~~
grow.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < V.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
3924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
7 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
215 ms |
1716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
2660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
3708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
3744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
338 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
4104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
5036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
