제출 #92784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92784		Retro3014	Growing Trees (BOI11_grow)	C++17	10 / 100	1093 ms	8940 KiB

grow

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <stdio.h>

#define MAX_N 100000
#define INF 2000000000
using namespace std;

int N, M;
struct S{
    int s, e;
    int l, r;
    int min, max, lazy;
};
vector<S> seg;
int arr[MAX_N+1];

deque<int> dq;

void init(){
    dq.push_back(0);
    int now=0;
    while(!dq.empty()){
        now=dq.front(); dq.pop_front();
        if(seg[now].s!=seg[now].e){
            seg[now].l=(int)seg.size(); seg.push_back({seg[now].s, (seg[now].s+seg[now].e)/2, -1, -1, 0, 0, 0}); dq.push_back(seg[now].l);
            seg[now].r=(int)seg.size(); seg.push_back({(seg[now].s+seg[now].e)/2+1, seg[now].e, -1, -1, 0, 0, 0}); dq.push_back(seg[now].r);
        }
    }
}

void init(int idx, int x, int y){
    if(seg[idx].s==seg[idx].e){
        seg[idx].min=y; seg[idx].max=y; return;
    }
    if(seg[seg[idx].l].e>=x){
        init(seg[idx].l, x, y);
    }else   init(seg[idx].r, x, y);
    seg[idx].max=max(seg[seg[idx].l].max, seg[seg[idx].r].max);
    seg[idx].min=min(seg[seg[idx].l].min, seg[seg[idx].r].min);
}

void calc(int idx){
    if(seg[idx].lazy>0){
        if(seg[idx].s!=seg[idx].e){
            seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
            seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
        }
        seg[idx].lazy=0;
    }
}

void update(int idx, int x, int y){
    calc(idx);
    if(seg[idx].s>y || seg[idx].e<x)    return;
    if(x<=seg[idx].s && seg[idx].e<=y){
        seg[idx].lazy++; seg[idx].min++; seg[idx].max++; return;
    }
    update(seg[idx].l, x, y); update(seg[idx].r, x, y);
    seg[idx].max=max(seg[seg[idx].l].max, seg[seg[idx].r].max);
    seg[idx].min=min(seg[seg[idx].l].min, seg[seg[idx].r].min);
}

int min(int idx, int x, int y){
    calc(idx);
    if(seg[idx].s>y || seg[idx].e<x)    return INF;
    if(x<=seg[idx].s && seg[idx].e<=y){
        return seg[idx].min;
    }
    return min(min(seg[idx].l, x, y), min(seg[idx].r, x, y));
}

int max(int idx, int x, int y){
    calc(idx);
    if(seg[idx].s>y || seg[idx].e<x)    return 0;
    if(x<=seg[idx].s && seg[idx].e<=y){
        return seg[idx].max;
    }
    return max(max(seg[idx].l, x, y), max(seg[idx].r, x, y));
}

int find(int idx, int x){
    calc(idx);
    if(seg[idx].s==seg[idx].e)  return seg[idx].max;
    if(x<=seg[seg[idx].l].e){
        return find(seg[idx].l, x);
    }
    return find(seg[idx].r, x);
}

int findl(int x, int y ,int z){
    int s=x, e=y, m=0;
    while(s<e){
        m=(s+e)/2;
        if(min(0, m, y)!=z){
            s=m+1;
        }else   e=m;
    }
    return s;
}

int findr(int x, int y, int z){
    int s=x, e=y, m=0;
    while(s<e){
        m=(s+e)/2+1;
        if(max(0, x, m)!=z){
            e=m-1;
        }else   s=m;
    }
    return s;
}

int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &N, &M);
    for(int i=0; i<N; i++)  scanf("%d", &arr[i]);
    seg.push_back({0, N-1, -1, -1, 0, 0, 0});
    init();
    sort(arr, arr+N);
    for(int i=0; i<N; i++){
        init(0, i, arr[i]);
    }
    char t; int a, b;
    int s, e, m, l, r;
    for(int i=0; i<M; i++){
        getchar();
        scanf("%c %d %d", &t, &a, &b);
        if(t=='F'){
            s=0; e=N-1;
            while(s<e){
                m=(s+e)/2;
                if(min(0, m, N-1)<b)    s=m+1;
                else   e=m;
            }
            e=min(N-1, s+a-1);
            l=findl(s, e, find(0, e));
            r=findr(e, N-1, find(0, e));
            //cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
            if(s<=l-1) update(0, s, l-1);
            if(r-e+l<=r)    update(0, r-e+l, r);
        }else{
            s=0; e=N;
            while(s<e){
                m=(s+e)/2;
                if(min(0, m, N)<a) s=m+1;
                else    e=m;
            }
            l=s; s=-1; e=N-1;
            while(s<e){
                m=(s+e)/2+1;
                if(max(0, -1, m)>b)  e=m-1;
                else    s=m;
            }
            r=s;
            //cout<<l<<" "<<r<<endl;
            printf("%d\n", max(0, r-l+1));
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

grow.cpp: In function 'int main()':
grow.cpp:117: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:118:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<N; i++)  scanf("%d", &arr[i]);
                             ~~~~~^~~~~~~~~~~~~~~
grow.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c %d %d", &t, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10