oj.uz

Submission #72250

# Submission time Handle Problem Language Result Execution time Memory
72250 2018-08-26T06:21:41 Z BOJ 8481(#2179, veydpz, jh05013, 16silver) Box Run (FXCUP3_box) C++17
100 / 100
 418 ms 15632 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], 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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 520 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 3 ms 524 KB Output is correct
8 Correct 2 ms 524 KB Output is correct
9 Correct 2 ms 524 KB Output is correct
10 Correct 2 ms 524 KB Output is correct
11 Correct 2 ms 652 KB Output is correct

Subtask #2
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 520 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 3 ms 524 KB Output is correct
8 Correct 2 ms 524 KB Output is correct
9 Correct 2 ms 524 KB Output is correct
10 Correct 2 ms 524 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 5 ms 724 KB Output is correct
14 Correct 31 ms 2152 KB Output is correct
15 Correct 44 ms 3276 KB Output is correct
16 Correct 55 ms 3848 KB Output is correct
17 Correct 161 ms 8272 KB Output is correct
18 Correct 248 ms 12152 KB Output is correct
19 Correct 311 ms 14100 KB Output is correct
20 Correct 418 ms 15632 KB Output is correct
21 Correct 347 ms 15632 KB Output is correct