oj.uz

답안 #72246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72246 2018-08-26T06:19:26 Z BOJ 8481(#2179, veydpz, jh05013, 16silver) 박스런 (FXCUP3_box) C++17
0 / 100
 3 ms 636 KB 
#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

template <typename T>
struct Segtree{
    T id = -1;
    T combine(T a, T b){
        return max(a, b);
    }
    
    int n; vector<T> arr;
    Segtree(int sz): n{1} {
        while(n < sz) n<<=1;
        arr.resize(n*2);
        fill(entire(arr), id);
    }
    void construct(vector<T>& A){
        for(size_t i=0; i<A.size(); i++) arr[n+i]= A[i];
        for(int i=n-1; i>=0; i--) arr[i] = combine(arr[2*i], arr[2*i+1]);
    }
    void update(int i, T val){
        for(arr[i+=n] = val; i > 1; i/= 2) arr[i/2] = combine(arr[i], arr[i^1]);
    }
    T query(int l, int r){
        T resl = id, resr = id;
        for(l+= n, r+= n+1; l < r; l/= 2, r/= 2){
            if(l&1) resl = combine(resl, arr[l++]);
            if(r&1) resr = combine(resr, arr[--r]);
        }
        return combine(resl, resr);
    }
};

vector<pair<int,int>> vc;
int H[500002], N, idx = 0;
int maxbox[500002];

int main(){OJize();
    // Compression
    cin>>N;
    for(int i=0;i<N;i++){
        int tmp; cin>>tmp;
        vc.push_back(make_pair(tmp,i));
    }
    sort(entire(vc));
    for(int i=0; i<N; i++){
        if(i==0 || vc[i].first != vc[i-1].first){idx++; H[vc[i].second]=idx;}
        else H[vc[i].second] = idx;
    }
    
    //for(int i=0; i<N; i++) cout<<H[i]<<' ';
    //cout<<'\n';
    
    // Store "max width box that could collide with wall i"
    Segtree<int> ST(N+2);
    
    for(int i=0; i<N; i++){
        maxbox[i] = i-1 - ST.query(H[i]+1, N+1);
        ST.update(H[i], i);
    }
    
    //for(int i=0;i<N;i++) cout<<maxbox[i]<<' ';
    //cout<<'\n';
    
    // Simulate box
    int wall = 0;
    for(int i=1; i<=N; i++){
        while(wall < N && maxbox[wall] < i) wall++;
        if(wall == N) cout << -1 << ' ';
        else cout << wall-i+1 << ' ';
    }
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Incorrect 3 ms 636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Incorrect 3 ms 636 KB Output isn't correct
6 Halted 0 ms 0 KB -