제출 #72124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72124		IDxTree (#118)	박스런 (FXCUP3_box)	C++17	100 / 100	159 ms	11564 KiB

box

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;

typedef pair<int,int> pii;
const int mx = 5e5 + 5, ms = 1.05e6;

struct Segtree{
    int n, seg[ms], *a;
    int _i(int now, int s, int e){
        //printf("_i(%d %d %d)\n",now,s,e);
        if(s == e){
        	//printf("seg[%d] = %d\n",now,a[s]);
	return seg[now] = a[s];
        }
        int m = (s+e)/2;
        seg[now] = max(_i(now<<1,s,m), _i(now<<1|1,m+1,e));
        //printf("seg[%d] = %d\n",now,seg[now]);
        return seg[now];
    }
    Segtree(){}
    Segtree(int n, int *a):n(n),a(a){
        //printf("n = %d, a = %p\n",n,a);
        _i(1,1,n);
    }
    int midx(int now, int s, int e, int l, int r, int v){
	//printf("midx(%d,%d,%d,%d,%d,%d)\n",now,s,e,l,r,v);
        if(e < l || s > r) return INT_MAX;
        if(seg[now] < v) return INT_MAX;

        if(l <= s && e <= r){
            if(s == e){
                //printf("end game. seg[%d] = %d, v = %d\n",now,seg[now],v);
                return seg[now] >= v ? s : INT_MAX;
            }
            int lf = now << 1, rg = lf | 1, m = (s+e)/2;
            if(seg[lf] >= v) return midx(lf,s,m,l,r,v);
            else return midx(rg,m+1,e,l,r,v);
        }
        int m = (s+e)/2;
        int lv = midx(now<<1,s,m,l,r,v);
        if(lv != INT_MAX) return lv;
        else return midx(now<<1|1,m+1,e,l,r,v);
    }
};

stack<pii> stk;
int n;
int h[mx], stop[mx];
void input(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    h[0] = INT_MAX;
    stk.emplace(h[0],0);
    for(int i = 1; i <= n; i++){
        while(!stk.empty() && stk.top().va < h[i]) stk.pop();
        stop[i] = i - stk.top().vb - 1;
        //printf("stop[%d] = %d\n",i,stop[i]);
        stk.emplace(h[i],i);
    }
    assert(!stk.empty());
}
void pro(){
    Segtree S(n,stop);
    for(int i = 1; i < n; i++){
        int m = S.midx(1,1,n,i+1,n,i);
        cout << (m == INT_MAX ? -1 : m-i) << ' ';
    }
    cout << -1 << '\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    input();
    pro();
}

• Subtask 1: 17 / 17
• Subtask 2: 83 / 83