Submission #956161

# Submission time Handle Problem Language Result Execution time Memory
956161 2024-04-01T08:15:40 Z n3rm1n Growing Trees (BOI11_grow) C++17
Compilation error
0 ms 0 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[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;
}

Compilation message

grow.cpp:61:8: error: 'int index' redeclared as different kind of entity
   61 | int x, index = -1;
      |        ^~~~~
In file included from /usr/include/string.h:432,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from grow.cpp:1:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
grow.cpp: In function 'int query(int, int, int)':
grow.cpp:69:21: error: overloaded function with no contextual type information
   69 |             index = l;
      |                     ^
grow.cpp:71:23: error: overloaded function with no contextual type information
   71 |         else index = -1;
      |                       ^
grow.cpp:72:16: error: cannot resolve overloaded function 'index' based on conversion to type 'int'
   72 |         return index;
      |                ^~~~~
grow.cpp:82:18: error: overloaded function with no contextual type information
   82 |         index = -1;
      |                  ^
grow.cpp:83:16: error: cannot resolve overloaded function 'index' based on conversion to type 'int'
   83 |         return index;
      |                ^~~~~
grow.cpp: In function 'void queries()':
grow.cpp:133:22: error: overloaded function with no contextual type information
  133 |             index = -1;
      |                      ^