Submission #160036

#	Time	Username	Problem	Language	Result	Execution time	Memory
160036		tushar_2658	Growing Trees (BOI11_grow)	C++14	0 / 100	835 ms	3008 KiB

grow

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

const int maxn = 200005;
int a[maxn], t[maxn], lazy[maxn];
int n, m;

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

void upd(int node, int b, int e, int i, int j){
    if(lazy[node] != 0){
        t[node] += (e - b + 1) * lazy[node]; 
        if(b != e){
            lazy[2*node] += lazy[node];
            lazy[2*node + 1] += lazy[node];
        }lazy[node] = 0;
    }
    if(i > e || j < b)return;
    if(b >= i && j >= e){
        t[node] += (e - b + 1);
        if(b != e){
            lazy[2*node]++;
            lazy[2*node + 1]++;
        }return;
    }int mid = (b + e)>>1; 
    upd(2*node, b, mid, i, j); 
    upd(2*node + 1, mid + 1, e, i, j);
    t[node] = t[2*node] + t[2*node + 1];
}

int query(int node, int b, int e, int i, int j){
    if(lazy[node] != 0){
        t[node] += (e - b + 1) * lazy[node];
        if(b != e){
            lazy[2*node] += lazy[node];
            lazy[2*node + 1] += lazy[node];
        }lazy[node] = 0;
    }
    if(i > e || j < b)return 0;
    if(b >= i && j >= e)return t[node];
    int mid = (b + e)>>1;
    return query(2*node, b, mid, i, j) + query(2*node + 1, mid + 1, e, i, j);
}

int query(int i, int j){
    if(i > j)return 0;
    return query(1, 1, n, i, j);
}

void upd(int i, int j){
    if(i > j)return;
    upd(1, 1, n, i, j);
}

int get_lowest(int h){
    int lo = 1, hi = n;
    while(lo <= hi){
        int mid = (lo + hi)>>1;
        if(query(mid, mid) >= h){
            hi = mid - 1;
        }else {
            lo = mid + 1;
        }
    }
    return lo;
}

int get_highest(int h){
    int lo = 1, hi = n, pos = n + 1;
    while(lo <= hi){
        int mid = (lo + hi)>>1;
        if(query(mid, mid) <= h){
            lo = mid + 1;
        }else {
            hi = mid - 1;
        }
    }
    return lo - 1;
}

int main(int argc, char const *argv[])
{
 //   freopen("in.txt", "r", stdin); 
    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 s[2];
        scanf("%s", s);
        if(s[0] == 'F'){
            int c, h;
            scanf("%d %d", &c, &h);
            if(query(n, n) < h)continue;
            int ff = get_lowest(h);
            int ss = -1;
            if(ff + c - 1 > n){
                ss = a[n];
            }else {
                ss = a[ff + c - 1];
            }
            int ll = get_highest(ss - 1);
            if(ll >= ff){
                upd(ff, ll);
                c -= (ll - ff + 1); 
            }
            ll = get_highest(ss);
            upd(ll - c + 1, ll);
        }else {
            int lo, hi;
            scanf("%d %d", &lo, &hi);
            if(lo > query(n, n) || query(1, 1) > hi){
                printf("0\n");
                continue;
            }
            lo = get_lowest(lo);
            hi = get_highest(hi);
            printf("%d\n", hi - lo + 1);
        }
    } 

    return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int get_highest(int)':
grow.cpp:77:25: warning: unused variable 'pos' [-Wunused-variable]
     int lo = 1, hi = n, pos = n + 1;
                         ^~~
grow.cpp: In function 'int main(int, const char**)':
grow.cpp:92: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:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
grow.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s);
         ~~~~~^~~~~~~~~
grow.cpp:104: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:122:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &lo, &hi);
             ~~~~~^~~~~~~~~~~~~~~~~~~

• 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