oj.uz

답안 #701044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701044 2023-02-19T21:18:58 Z Ahmed57 Growing Trees (BOI11_grow) C++14
100 / 100
 305 ms 6932 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;
    propgate(p*2,l,md);
    propgate(p*2+1,md+1,r);
    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[p];
    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(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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;
            propgate(1,1,n);
            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{
            propgate(1,1,n);
            int l,r;
            cin>>l>>r;
            if(seg[1]<r){
                continue;
            }
            int ind = lowe(1,1,n,r);
            int val = ge(1,1,n,ind);
            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);
            int ind3 = 0;
            if(seg[1]<=d)ind3 = n+1;
            else ind3 = lowe(1,1,n,d+1);
            int len = (ind+l-1)-ind2+1;
            if(d!=val){
                update(1,1,n,ind,ind2-1);
            }
            update(1,1,n,ind3-len,ind3-1);
        }
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 5240 KB Output is correct
2 Correct 212 ms 6780 KB Output is correct
3 Correct 125 ms 6732 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 8 ms 448 KB Output is correct
3 Correct 8 ms 444 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 146 ms 1632 KB Output is correct
6 Correct 213 ms 1948 KB Output is correct
7 Correct 9 ms 576 KB Output is correct
8 Correct 173 ms 1468 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 1028 KB Output is correct
2 Correct 216 ms 1988 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 174 ms 1692 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 1148 KB Output is correct
2 Correct 198 ms 1952 KB Output is correct
3 Correct 18 ms 724 KB Output is correct
4 Correct 200 ms 1944 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 3044 KB Output is correct
2 Correct 205 ms 6348 KB Output is correct
3 Correct 48 ms 1824 KB Output is correct
4 Correct 96 ms 6348 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 5012 KB Output is correct
2 Correct 207 ms 6476 KB Output is correct
3 Correct 102 ms 6584 KB Output is correct
4 Correct 52 ms 1852 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 5164 KB Output is correct
2 Correct 171 ms 6444 KB Output is correct
3 Correct 117 ms 6764 KB Output is correct
4 Correct 44 ms 1864 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 5228 KB Output is correct
2 Correct 204 ms 6288 KB Output is correct
3 Correct 53 ms 5820 KB Output is correct
4 Correct 175 ms 6232 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 5324 KB Output is correct
2 Correct 234 ms 6708 KB Output is correct
3 Correct 245 ms 6932 KB Output is correct

Subtask #10
10.0 / 10.0

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