Submission #72256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72256	2018-08-26T06:27:40 Z	호우주의보(#2154, leehosu01)	Box Run (FXCUP3_box)	C++17	100 / 100	971 ms	32992 KB

box

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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