oj.uz

답안 #160041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160041 2019-10-25T18:09:28 Z tushar_2658 Growing Trees (BOI11_grow) C++14
0 / 100
 814 ms 3520 KB 
#include "bits/stdc++.h"
using namespace std; 
 
const int maxn = 200005;
int a[maxn], t[maxn << 2], lazy[maxn << 2];
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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 134 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 114 ms 700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 121 ms 1760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 2744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 814 ms 3232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 168 ms 2824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 700 ms 3520 KB Output isn't correct