oj.uz

Submission #701036

# Submission time Handle Problem Language Result Execution time Memory
701036 2023-02-19T20:37:16 Z Ahmed57 Growing Trees (BOI11_grow) C++14
0 / 100
 241 ms 7480 KB 
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std;
long long seg[400001];
long long lazy[400001];
long long arr[100001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = arr[l];
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
void propgate(int p,int l,int r){
    seg[p]+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] =0;
}
int lowe(int p,int l,int r,int x){
    propgate(p,l,r);
    if(l==r)return l;
    int md = (l+r)/2;
    if(seg[p*2]>=x)return lowe(p*2,l,md,x);
    else return lowe(p*2+1,md+1,r,x);
}int ge(int p,int l,int r,int ind){
    propgate(p,l,r);
    if(l==r)return seg[l];
    int md = (l+r)/2;
    if(ind<=md)return ge(p*2,l,md,ind);
    else return ge(p*2+1,md+1,r,ind);
}void update(int p,int l,int r,int lq,int rq){
    propgate(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=1;
        propgate(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq);update(p*2+1,md+1,r,lq,rq);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
int main(){
    int n,q;
    cin>>n>>q;
    for(int i = 1;i<=n;i++)cin>>arr[i];
    sort(arr+1,arr+n+1);
    build(1,1,n);
    while(q--){
        char c;cin>>c;
        if(c=='C'){
            int l,r;cin>>l>>r;
            if(seg[1]<l){
                cout<<0<<endl;
                continue;
            }
            int ind1 = lowe(1,1,n,l);
            if(seg[1]<r+1){
                cout<<n-ind1+1<<endl;
                continue;
            }
            int ind2 =lowe(1,1,n,r+1);
            cout<<ind2-ind1<<endl;
        }else{
            int l,r;
            cin>>l>>r;
            if(seg[1]<r){
                continue;
            }
            int ind = lowe(1,1,n,r);
            if(ind+l-1>=n){
                update(1,1,n,ind,n);
                continue;
            }
            int d = ge(1,1,n,ind+l-1);
            int ind2 = lowe(1,1,n,d);
            if(ind2-1>=ind){
                update(1,1,n,ind,ind2-1);
            }
            int ind3 = lowe(1,1,n,d+1);
            int len = (ind+l-1)-ind2+1;
            update(1,1,n,ind3-len,ind3-1);
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 6204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 1672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 3896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 5904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 6032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 186 ms 6824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 6408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 7480 KB Output isn't correct
2 Halted 0 ms 0 KB -