Submission #956164

#	Time	Username	Problem	Language	Result	Execution time	Memory
956164		n3rm1n	Growing Trees (BOI11_grow)	C++17	0 / 100	116 ms	5888 KiB

grow

#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 (stderr)

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;
      |         ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10