oj.uz

답안 #92804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92804 2019-01-05T04:20:06 Z Retro3014 Growing Trees (BOI11_grow) C++17
10 / 100
 1000 ms 8936 KB 
#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){
    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;
    }
    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){
    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;
    }
    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){
    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;
    }
    if(seg[idx].s>y || seg[idx].e<x)    return -1;
    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){
    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;
    }
    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(find(0, m)!=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(find(0, m)!=z) e=m-1;
        else   s=m;
    }
    return s;
}

int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d%d", &N, &M);
    //N=MAX_N+1; M=MAX_N+1;
    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]);
    }*/
    for(int i=(int)seg.size()-1; i>=0; i--){
        if(seg[i].s==seg[i].e){
            seg[i].max=seg[i].min=arr[seg[i].s];
        }else{
            seg[i].max=max(seg[seg[i].l].max, seg[seg[i].r].max);
            seg[i].min=min(seg[seg[i].l].min, seg[seg[i].r].min);
        }
    }
    char t; int a, b;
    int s, e, m, l, r;
    for(int i=0; i<M; i++){
        scanf("%c", &t);
        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;
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:140: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:142: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:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", &t);
         ~~~~~^~~~~~~~~~
grow.cpp:161: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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 8652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Execution timed out 1075 ms 632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1086 ms 1056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1082 ms 1056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1081 ms 4844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 722 ms 8556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 8432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 898 ms 8680 KB Output is correct
2 Execution timed out 1083 ms 8552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 8556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

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