| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 956161 | n3rm1n | Growing Trees (BOI11_grow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[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, index = -1;
int query(int i, int l, int r)
{
push_lazy(i, l, r);
if(l == r)
{
if(tmax[i] > x)
{
index = l;
}
else index = -1;
return index;
}
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)
{
index = -1;
return index;
}
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 indexl = 0, indexr = 0;
int c, h;
while(m --)
{
cin >> type >> xx >> yy;
// cout << "on query " << type << " " << xx << " " << yy << endl;
if(type == 'C')
{
index = -1;
x = xx-1;
indexl = query(1, 1, n);
x = yy;
indexr = query(1, 1, n) - 1;
if(indexl == -1)
{
cout << 0 << endl;
continue;
}
if(indexr <= -1)
{
indexr = n;
}
//cout << "after query C: " << indexl << " and " << indexr << endl;
cout <<indexr - indexl + 1 << endl;
// cout << endl;
}
else
{
c = xx;
h = yy;
x = h-1;
indexl = query(1, 1, n);
if(indexl == -1)continue;
indexr = min(n, indexl + xx - 1);
//cout << "initial segm " << indexl << " " << indexr << endl;
val = indexr;
int last = get(1, 1, n);
//cout << "last is " << last << endl;
x = last - 1;
int first_last = query(1, 1, n);
ql = indexl;
qr = first_last-1;
int sz = qr - ql + 1;
//cout << "first update " << ql << " " << qr << endl;
int left = (indexr - indexl + 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;
}