#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int n, m, a[MAXN];
int tmin[MAXN * 4], tmax[MAXN * 4], lazy[4 * MAXN];
void read()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
sort(a+1, a+n+1);
for (int i = 1; i <= 4*n; ++ i)
{
tmin[i] = 1e9+2e5;
tmax[i] = -1;
}
// cout << tmin[1] << endl;
}
/// make tree (ako mi potrqbva neshto)
void make_tree(int i, int l, int r)
{
if(l == r)
{
tmin[i] = a[l];
tmax[i] = a[r];
return;
}
int mid = (l + r)/2;
make_tree(2*i, l, mid);
make_tree(2*i+1, mid+1, r);
tmin[i] = min(tmin[2*i], tmin[2*i+1]);
tmax[i] = max(tmax[2*i], tmax[2*i+1]);
}
void push_lazy(int i, int l, int r)
{
//cout << i << " " << lazy[i] << endl;
if(lazy[i])
{
tmin[i] += lazy[i];
tmax[i] += lazy[i];
}
if(l != r)
{
lazy[2*i] += lazy[i];
lazy[2*i+1] += lazy[i];
}
lazy[i] = 0;
}
/// pyrvoto > x
int x, id = -1;
int query(int i, int l, int r)
{
push_lazy(i, l, r);
if(l == r)
{
if(tmax[i] > x)
{
id = l;
}
else id = -1;
return id;
}
int mid = (l + r)/2;
push_lazy(2*i, l, mid);
push_lazy(2*i+1, mid+1, r);
int maxleft = tmax[2*i];
int maxright = tmax[2*i+1];
if(maxleft <= x && maxright <= x)
{
id = -1;
return id;
}
if(maxleft <= x)return query(2*i+1, mid+1, r);
else return query(2*i, l, mid);
}
int ql, qr;
void update(int i, int l, int r)
{
push_lazy(i, l, r);
if(qr < l || ql > r)return;
if(ql <= l && r <= qr)
{
lazy[i] ++;
push_lazy(i, l, r);
//cout << "changed to" << tmin[i] << ", "<< lazy[i] << endl;
return;
}
int mid = (l + r)/2;
update(2*i, l, mid);
update(2*i+1, mid+1, r);
tmax[i] = max(tmax[2*i], tmax[2*i+1]);
tmin[i] = min(tmin[2*i], tmin[2*i+1]);
}
int val;
int get(int i, int l, int r)
{
push_lazy(i, l, r);
if(l == r)
{
return tmin[i];
}
int mid = (l + r)/2;
if(val <= mid)return get(2*i, l, mid);
else return get(2*i+1, mid+1, r);
}
void queries()
{
char type;
int xx, yy;
int idl = 0, idr = 0;
int c, h;
while(m --)
{
cin >> type >> xx >> yy;
// cout << "on query " << type << " " << xx << " " << yy << endl;
if(type == 'C')
{
id = -1;
x = xx-1;
idl = query(1, 1, n);
x = yy;
idr = query(1, 1, n) - 1;
if(idl == -1)
{
cout << 0 << endl;
continue;
}
if(idr <= -1)
{
idr = n;
}
//cout << "after query C: " << idl << " and " << idr << endl;
cout <<idr - idl + 1 << endl;
// cout << endl;
}
else
{
c = xx;
h = yy;
x = h-1;
idl = query(1, 1, n);
if(idl == -1)continue;
idr = min(n, idl + xx - 1);
//cout << "initial segm " << idl << " " << idr << endl;
val = idr;
int last = get(1, 1, n);
//cout << "last is " << last << endl;
x = last - 1;
int first_last = query(1, 1, n);
ql = idl;
qr = first_last-1;
int sz = qr - ql + 1;
//cout << "first update " << ql << " " << qr << endl;
int left = (idr - idl + 1) - sz;
if(ql <= qr)update(1, 1, n);
x = last;
int first_next = query(1, 1, n);
qr = first_next - 1;
ql = first_next - left;
if(ql <= qr)update(1, 1, n);
//cout << "current array is: " << endl;
/*for (int i = 1; i <= n; ++ i)
{
val = i;
cout << get(1, 1, n) << " ";
}
cout << endl;
cout << endl;*/
}
}
}
int main()
{
speed();
read();
make_tree(1, 1, n);
/*cout << "starting array: " << endl;
for (int i = 1; i <= n; ++ i)
{
val = i;
cout << get(1, 1, n) << " ";
}
cout << endl;
cout << endl;*/
queries();
return 0;
}
Compilation message
grow.cpp: In function 'void queries()':
grow.cpp:126:9: warning: variable 'c' set but not used [-Wunused-but-set-variable]
126 | int c, h;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
5208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
4712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
5540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
5268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
