oj.uz

답안 #137489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137489 2019-07-28T04:47:47 Z gs14004 Growing Trees (BOI11_grow) C++17
100 / 100
 204 ms 5096 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
int n, q;
int a[100005];
 
struct seg{
    int tree[270000], lazy[270000];
    void lazydown(int p){
        tree[2*p] += lazy[p];
        tree[2*p+1] += lazy[p];
        lazy[2*p] += lazy[p];
        lazy[2*p+1] += lazy[p];
        lazy[p] = 0;
    }
    void add(int s, int e, int ps, int pe, int p, int v){
        if(e < ps || pe < s) return;
        if(s <= ps && pe <= e){
            tree[p] += v;
            lazy[p] += v;
            return;
        }
        int pm = (ps + pe) / 2;
        lazydown(p);
        add(s,e,ps,pm,2*p,v);
        add(s,e,pm+1,pe,2*p+1,v);
        tree[p] = max(tree[2*p], tree[2*p+1]);
    }
    int lower_bound(int ps, int pe, int p, int val){
        if(tree[1] < val) return n+1;
        if(ps == pe) return ps;
        int pm = (ps + pe) / 2;
        lazydown(p);
        if(tree[2*p] < val) return lower_bound(pm+1,pe,2*p+1,val);
        else return lower_bound(ps,pm,2*p,val);
    }
    int getval(int pos, int ps, int pe, int p){
        if(ps == pe) return tree[p];
        int pm = (ps + pe) / 2;
        lazydown(p);
        if(pos <= pm) return getval(pos,ps,pm,2*p);
        return getval(pos,pm+1,pe,2*p+1);
    }
    void dfs(int ps, int pe, int p){
        if(ps == pe){
            printf("%d ",tree[p]);
            return;
        }
        lazydown(p);
        dfs(ps,(ps+pe)/2,2*p);
        dfs((ps+pe)/2+1,pe,2*p+1);
    }
}seg;
 
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=1; i<=n; i++){
        seg.add(i,i,1,n,1,a[i]);
    }
    while(q--){
        char str[5];
        int x, y;
        scanf("%s %d %d",str,&y,&x);
        if(str[0] == 'F'){
            int st = seg.lower_bound(1,n,1,x);
            if(st == n+1) continue;
            int ed = min(st + y - 1, n);
            int val = seg.getval(ed,1,n,1);
            int t = seg.lower_bound(1,n,1,val);
            int cnt = ed - t + 1;
            int u = seg.lower_bound(1,n,1,val + 1);
            seg.add(st, t - 1, 1, n, 1, 1);
            seg.add(u - cnt, u - 1, 1, n, 1, 1);
        }
        else{
            swap(x,y);
            int t = seg.lower_bound(1,n,1,y+1);
            int u = seg.lower_bound(1,n,1,x);
            printf("%d\n",t - u);
        }
    }
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
grow.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~
grow.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s %d %d",str,&y,&x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 4216 KB Output is correct
2 Correct 165 ms 4472 KB Output is correct
3 Correct 137 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 57 ms 1580 KB Output is correct
6 Correct 69 ms 1784 KB Output is correct
7 Correct 8 ms 504 KB Output is correct
8 Correct 38 ms 1272 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 1760 KB Output is correct
2 Correct 69 ms 1900 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 47 ms 1400 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 2012 KB Output is correct
2 Correct 76 ms 1916 KB Output is correct
3 Correct 13 ms 504 KB Output is correct
4 Correct 69 ms 1980 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 2756 KB Output is correct
2 Correct 146 ms 4088 KB Output is correct
3 Correct 24 ms 1272 KB Output is correct
4 Correct 109 ms 4088 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 3844 KB Output is correct
2 Correct 152 ms 4188 KB Output is correct
3 Correct 128 ms 4324 KB Output is correct
4 Correct 26 ms 1272 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 3832 KB Output is correct
2 Correct 110 ms 4068 KB Output is correct
3 Correct 135 ms 4392 KB Output is correct
4 Correct 24 ms 1272 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 4500 KB Output is correct
2 Correct 146 ms 4156 KB Output is correct
3 Correct 63 ms 3448 KB Output is correct
4 Correct 105 ms 3960 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 4216 KB Output is correct
2 Correct 193 ms 4552 KB Output is correct
3 Correct 204 ms 4568 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 5096 KB Output is correct