oj.uz

답안 #72256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72256 2018-08-26T06:27:40 Z 호우주의보(#2154, leehosu01) 박스런 (FXCUP3_box) C++17
100 / 100
 971 ms 32992 KB 
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,M;
vector<tuple<int,int> >V;
set<int> S;
int lenn[500005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    fill (lenn,lenn+N+1,N+1);
    V.push_back(make_tuple(-1000000001,0));
    for(int i=1;i<=N;i++)
    {
        int T;
        cin>>T;
        V.push_back(make_tuple(-T,i));
    }
    sort(V.begin(),V.end());
    for(int i=0;i<V.size();)
    {
        for(int j=i;get<0>(V[i])==get<0>(V[j]);j++)
            S.insert(get<1>(V[j]));
        for(int j=i;get<0>(V[i])==get<0>(V[j]);j++)
        {
            auto K=S.lower_bound(get<1>(V[j]));
            if(K!=S.begin())
            {
                int&R=lenn[get<1>(V[j])-*(--K)-1];
                R=min(R,get<1>(V[j]));
            }
        }
        for(i++;get<0>(V[i])==get<0>(V[i-1]);i++);
    }
    for(int i=N-1;i;i--)lenn[i]=min(lenn[i],lenn[i+1]);
    for(int i=1;i<=N;i++)
    {
        if(lenn[i]==N+1)printf("-1 ");
        else printf("%d ",lenn[i]-i);
    }
}

Compilation message

box.cpp: In function 'int main()':
box.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<V.size();)
                 ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 3 ms 516 KB Output is correct
7 Correct 3 ms 516 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 3 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 3 ms 664 KB Output is correct

Subtask #2
83.0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 3 ms 516 KB Output is correct
7 Correct 3 ms 516 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 3 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 3 ms 664 KB Output is correct
12 Correct 2 ms 664 KB Output is correct
13 Correct 4 ms 676 KB Output is correct
14 Correct 41 ms 3484 KB Output is correct
15 Correct 90 ms 5436 KB Output is correct
16 Correct 119 ms 6948 KB Output is correct
17 Correct 425 ms 17100 KB Output is correct
18 Correct 590 ms 23260 KB Output is correct
19 Correct 890 ms 29180 KB Output is correct
20 Correct 971 ms 32992 KB Output is correct
21 Correct 912 ms 32992 KB Output is correct