oj.uz

답안 #72124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72124 2018-08-26T05:24:24 Z IDxTree(#2155, TAMREF, imeimi2000, Diuven) 박스런 (FXCUP3_box) C++17
100 / 100
 159 ms 11564 KB 
#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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 2 ms 616 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 2 ms 616 KB Output is correct

Subtask #2
83.0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 2 ms 616 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 2 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 15 ms 1636 KB Output is correct
15 Correct 22 ms 2608 KB Output is correct
16 Correct 35 ms 2948 KB Output is correct
17 Correct 74 ms 6052 KB Output is correct
18 Correct 110 ms 9204 KB Output is correct
19 Correct 144 ms 10652 KB Output is correct
20 Correct 159 ms 11564 KB Output is correct
21 Correct 151 ms 11564 KB Output is correct