oj.uz

Submission #956169

# Submission time Handle Problem Language Result Execution time Memory
956169 2024-04-01T08:39:11 Z n3rm1n Growing Trees (BOI11_grow) C++17
100 / 100
 160 ms 7252 KB 
#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;
    }
}

void make_tree(int i, int l, int r)
{
    if(l == r)
    {
        tmin[i] = a[l];
        tmax[i] = a[l];
        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)
{
    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;
}


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);
        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]);
    return;
}


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')
        {

            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 == -2)
            {
                idr = n;
            }
            cout << max(0, idr - idl + 1) << endl;
        }
        else
        {
            c = xx;
            h = yy;

            x = h-1;
            idl = query(1, 1, n);
            if(idl == -1)continue;
            idr = min(n, idl + c - 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);
            if(first_next == -1)first_next = n + 1;
            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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 6204 KB Output is correct
2 Correct 113 ms 6836 KB Output is correct
3 Correct 98 ms 6712 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 45 ms 5716 KB Output is correct
6 Correct 51 ms 5848 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 28 ms 5212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5712 KB Output is correct
2 Correct 50 ms 5928 KB Output is correct
3 Correct 2 ms 4880 KB Output is correct
4 Correct 35 ms 5476 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5716 KB Output is correct
2 Correct 54 ms 5804 KB Output is correct
3 Correct 11 ms 4768 KB Output is correct
4 Correct 50 ms 5972 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 6092 KB Output is correct
2 Correct 101 ms 6200 KB Output is correct
3 Correct 14 ms 5212 KB Output is correct
4 Correct 86 ms 6388 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 5744 KB Output is correct
2 Correct 103 ms 6484 KB Output is correct
3 Correct 93 ms 6648 KB Output is correct
4 Correct 14 ms 5208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6056 KB Output is correct
2 Correct 66 ms 6600 KB Output is correct
3 Correct 101 ms 6736 KB Output is correct
4 Correct 13 ms 5212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6272 KB Output is correct
2 Correct 102 ms 6228 KB Output is correct
3 Correct 25 ms 6028 KB Output is correct
4 Correct 69 ms 6604 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6228 KB Output is correct
2 Correct 101 ms 6740 KB Output is correct
3 Correct 160 ms 7164 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7252 KB Output is correct