Submission #72250

#	Time	Username	Problem	Language	Result	Execution time	Memory
72250		BOJ 8481 (#118)	Box Run (FXCUP3_box)	C++17	100 / 100	418 ms	15632 KiB

box

#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], 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: 17 / 17
• Subtask 2: 83 / 83