oj.uz

Submission #287395

# Submission time Handle Problem Language Result Execution time Memory
287395 2020-08-31T16:40:30 Z Namnamseo Growing Trees (BOI11_grow) C++17
100 / 100
 273 ms 4344 KB 
#include <cstdio>
#include <algorithm>

int n,m;

int mt  [262144];
int lazy[262144];

int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }

void update(int pos,int ml,int mr,int l,int r){
    if(pos<131072){
        mt  [pos*2  ]+=lazy[pos];
        lazy[pos*2  ]+=lazy[pos];
        mt  [pos*2+1]+=lazy[pos];
        lazy[pos*2+1]+=lazy[pos];
        lazy[pos]=0;
    }
    if(l<=ml && mr<=r){
        ++mt[pos]; ++lazy[pos];
    } else if(mr<l || r<ml) return;
    else {
        int m=(ml+mr)/2;
        update(pos*2  ,ml ,m ,l,r);
        update(pos*2+1,m+1,mr,l,r);
        mt[pos]=max(mt[pos*2],mt[pos*2+1]);
    }
}

inline void update(int l,int r){ if(l<=r) update(1,0,131071,l,r); }

int findLeftIsang(int val){
    int pos=1;
    if(mt[pos]<val) return n;
    while(pos<131072){
        mt  [pos*2  ]+=lazy[pos];
        lazy[pos*2  ]+=lazy[pos];
        mt  [pos*2+1]+=lazy[pos];
        lazy[pos*2+1]+=lazy[pos];
        lazy[pos]=0;
        pos*=2;
        if(mt[pos]<val) ++pos;
    }
    return pos-131072;
}

void printAll(){
    int i;
    for(i=1;i<131072;++i){
        mt  [i*2  ]+=lazy[i];
        lazy[i*2  ]+=lazy[i];
        mt  [i*2+1]+=lazy[i];
        lazy[i*2+1]+=lazy[i];
        lazy[i]=0;
    }
    for(i=0;i<n;++i) printf("%d ",mt[131072+i]);
    putchar(10);
}

void back_propagate(int index){
    if(index>1){
        back_propagate(index/2);
    }
    if(index<131072){
        mt  [index*2  ]+=lazy[index];
        mt  [index*2+1]+=lazy[index];
        lazy[index*2  ]+=lazy[index];
        lazy[index*2+1]+=lazy[index];
        lazy[index]=0;
    }
}

int to_upd_left[10];
int to_upd_right[10];
int to_upd_ind;

inline void queue(int l,int r){ to_upd_left[to_upd_ind]=l, to_upd_right[to_upd_ind]=r, ++to_upd_ind; }
inline void flush() { for(;to_upd_ind--;) update(to_upd_left[to_upd_ind],to_upd_right[to_upd_ind]); ++to_upd_ind; }

int main(){
    scanf("%d%d",&n,&m);
    int i;
    for(i=0;i<n;++i) scanf("%d",mt+131072+i);
    std::sort(mt+131072,mt+131072+n);
    for(i=131071;i>=1;--i) mt[i]=max(mt[i*2],mt[i*2+1]);
    char com;
    int a,b;
    int k;
    int p,q,r,s, minval, maxval;
    for(;m--;){
        getchar();
        scanf("%c%d%d",&com,&a,&b);
        if(com=='F'){
            if(mt[1]<b) continue;
            p = findLeftIsang(b);
            q = findLeftIsang(mt[131072+p]+1);
            if(q-p >= a) queue(q-a,q-1);
            else {
                queue(p,q-1);
                a-=q-p;
                if(q+a-1>n-1) queue(q,n-1);
                else {
                    back_propagate(q+a-1+131072);
                    maxval = mt[q+a-1+131072];
                    r = findLeftIsang(maxval);
                    s = findLeftIsang(maxval+1);
                    k=a-(r-q);
                    queue(s-k,s-1);
                    queue(q,q+a-k-1);
                }
            }
            flush();
        } else if(com=='C'){
            b=findLeftIsang(b+1);
            a=findLeftIsang(a);
            printf("%d\n",b-a);
        }
    }
    return 0;
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:90:18: warning: unused variable 'minval' [-Wunused-variable]
   90 |     int p,q,r,s, minval, maxval;
      |                  ^~~~~~
grow.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
grow.cpp:84:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     for(i=0;i<n;++i) scanf("%d",mt+131072+i);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~
grow.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         scanf("%c%d%d",&com,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3320 KB Output is correct
2 Correct 197 ms 3576 KB Output is correct
3 Correct 231 ms 3480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 70 ms 2040 KB Output is correct
6 Correct 87 ms 2168 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 70 ms 1656 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2296 KB Output is correct
2 Correct 98 ms 2424 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 73 ms 1912 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2460 KB Output is correct
2 Correct 92 ms 2296 KB Output is correct
3 Correct 19 ms 1024 KB Output is correct
4 Correct 81 ms 2424 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 2784 KB Output is correct
2 Correct 168 ms 3220 KB Output is correct
3 Correct 24 ms 1536 KB Output is correct
4 Correct 185 ms 3160 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2936 KB Output is correct
2 Correct 154 ms 3192 KB Output is correct
3 Correct 250 ms 3316 KB Output is correct
4 Correct 21 ms 1496 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3048 KB Output is correct
2 Correct 120 ms 3320 KB Output is correct
3 Correct 254 ms 3504 KB Output is correct
4 Correct 21 ms 1528 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 3568 KB Output is correct
2 Correct 165 ms 3196 KB Output is correct
3 Correct 49 ms 2808 KB Output is correct
4 Correct 103 ms 3064 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 3448 KB Output is correct
2 Correct 173 ms 3576 KB Output is correct
3 Correct 273 ms 3832 KB Output is correct

Subtask #10
10.0 / 10.0

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