oj.uz

Submission #160053

# Submission time Handle Problem Language Result Execution time Memory
160053 2019-10-25T19:19:31 Z tushar_2658 Growing Trees (BOI11_grow) C++14
100 / 100
 419 ms 5888 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 4088 KB Output is correct
2 Correct 306 ms 5888 KB Output is correct
3 Correct 78 ms 5496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 14 ms 376 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 11 ms 632 KB Output is correct
5 Correct 278 ms 1692 KB Output is correct
6 Correct 376 ms 1912 KB Output is correct
7 Correct 14 ms 632 KB Output is correct
8 Correct 266 ms 1320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 1036 KB Output is correct
2 Correct 331 ms 2052 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 299 ms 1684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 1136 KB Output is correct
2 Correct 371 ms 2108 KB Output is correct
3 Correct 15 ms 636 KB Output is correct
4 Correct 340 ms 2152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 2296 KB Output is correct
2 Correct 291 ms 5084 KB Output is correct
3 Correct 82 ms 1528 KB Output is correct
4 Correct 65 ms 5212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 3856 KB Output is correct
2 Correct 307 ms 5240 KB Output is correct
3 Correct 77 ms 5368 KB Output is correct
4 Correct 80 ms 1784 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 4024 KB Output is correct
2 Correct 259 ms 5112 KB Output is correct
3 Correct 78 ms 5496 KB Output is correct
4 Correct 81 ms 1700 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 3960 KB Output is correct
2 Correct 312 ms 5112 KB Output is correct
3 Correct 58 ms 4728 KB Output is correct
4 Correct 250 ms 4984 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 4088 KB Output is correct
2 Correct 312 ms 5496 KB Output is correct
3 Correct 244 ms 5768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 4344 KB Output is correct