Submission #160053

#	Time	Username	Problem	Language	Result	Execution time	Memory
160053		tushar_2658	Growing Trees (BOI11_grow)	C++14	100 / 100	419 ms	5888 KiB

grow

#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;
int a[maxn], lazy[maxn << 2];
pair<int, int> t[maxn << 2];

void build(int node, int b, int e){
    if(b == e){
        t[node].first = a[b]; 
        t[node].second = a[b];
        return;
    }int mid = (b + e)>>1;
    build(2*node, b, mid);
    build(2*node + 1, mid + 1, e);
    t[node].first = max(t[2*node].first, t[2*node + 1].first);
    t[node].second = min(t[2*node].second, t[2*node + 1].second);
}

void push(int node, int b, int e){
    if(lazy[node] != 0){
        t[node].first += lazy[node];
        t[node].second += lazy[node];
        if(b != e){
            lazy[2*node] += lazy[node];
            lazy[2*node + 1] += lazy[node];
        }lazy[node] = 0;
    }
}

void update(int node, int b, int e, int i, int j){
    if(i > j)return;
    if(lazy[node] != 0){
        push(node, b, e);
    }
    if(i > e || j < b)return;
    if(b >= i && j >= e){
        t[node].first++;
        t[node].second++;
        if(b != e){
            lazy[2*node]++;
            lazy[2*node + 1]++;
        }return;
    }int mid = (b + e)>>1;
    update(2*node, b, mid, i, j); 
    update(2*node + 1, mid + 1, e, i, j);
    t[node].first = max(t[2*node].first, t[2*node + 1].first);
    t[node].second = min(t[2*node].second, t[2*node + 1].second);
}

int f_pos(int node, int b, int e, int val){
    if(lazy[node]){
        push(node, b, e);
    }
    if(b == e){
        if(t[node].first >= val)return b;
        return -1;
    }int mid = (b + e)>>1;
    push(2*node, b, mid);
    push(2*node + 1, mid + 1, e);
    if(t[2*node].first >= val){
        return f_pos(2*node, b, mid, val);
    }else {
        return f_pos(2*node + 1, mid + 1, e, val);
    }
}

int l_pos(int node, int b, int e, int val){
    if(lazy[node] != 0){
        push(node, b, e);
    }
    if(b == e){
        if(t[node].first <= val)return b;
        return -1;
    }
    int mid = (b + e)>>1;
    push(2*node, b, mid);
    push(2*node + 1, mid + 1, e);
    if(t[2*node + 1].second <= val){
        return l_pos(2*node + 1, mid + 1, e, val);
    }else {
        return l_pos(2*node, b, mid, val);
    }
}

int at_pos(int node, int b, int e, int i){
    if(lazy[node]){
        push(node, b, e);
    }
    if(b == e){
        return t[node].first;
    }
    int mid = (b + e)>>1;
    push(2*node, b, mid);
    push(2*node + 1, mid + 1, e);
    if(i <= mid){
        return at_pos(2*node, b, mid, i);
    }else {
        return at_pos(2*node + 1, mid + 1, e, i);
    }
}

int main(int argc, char const *argv[])
{
//    freopen("in.txt", "r", stdin);
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    build(1, 1, n); 

    while(m--){
        char ch;
        cin >> ch; 
        if(ch == 'F'){
            int c, h;
            scanf("%d %d", &c, &h);
            int pos1 = f_pos(1, 1, n, h);
            if(pos1 == -1)continue;
            int pos2 = -1;
            if(pos1 + c - 1 >= n){
                update(1, 1, n, pos1, n);
                continue;
            }
            pos2 = min(n, pos1 + c - 1);
            int last_v = at_pos(1, 1, n, pos2);
            int li = f_pos(1, 1, n, last_v);
            int ri = l_pos(1, 1, n, last_v);
            if(at_pos(1, 1, n, li) == at_pos(1, 1, n, pos1)){
                update(1, 1, n, ri - c + 1, ri); 
                continue;
            }
            update(1, 1, n, pos1, li - 1);
            int need = c - (li - pos1);
            update(1, 1, n, ri - need + 1, ri);
        }else {
            int l, r; 
            scanf("%d %d", &l, &r);
            if(f_pos(1, 1, n, l) == -1 || l_pos(1, 1, n, r) == -1){
                printf("0\n");
                continue;
            }
            printf("%d\n", l_pos(1, 1, n, r) - f_pos(1, 1, n, l) + 1); 
        }
    }

    return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int main(int, const char**)':
grow.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
grow.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &c, &h);
             ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:140:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &l, &r);
             ~~~~~^~~~~~~~~~~~~~~~~

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