Submission #71964

#	Time	Username	Problem	Language	Result	Execution time	Memory
71964		이시대의진정한망겜스타투 (#118)	Box Run (FXCUP3_box)	C++17	100 / 100	209 ms	30772 KiB

box

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int N, H[500050];
int ans[2][500050];

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) scanf("%d", H+i);
	H[0] = H[N + 1] = 1e9 + 10;
	vector <pii> V;
	for(int i=1;i<=N;i++) ans[0][i] = ans[1][i] = 1e9;
	for(int i=0;i<=N+1;i++) {
		while(szz(V) && V.back().Fi < H[i]) V.pop_back();
		if(szz(V)) {
			int d = i - V.back().Se - 1;
			if(d) {
				ans[0][d] = min(ans[0][d], i);
			}
		}
		V.push_back(pii(H[i], i));
	}
	for(int i=N-1;i;i--) ans[0][i] = min(ans[0][i], ans[0][i+1]);
	V.clear();
	for(int i=N+1;i>=0;i--) {
		while(szz(V) && V.back().Fi < H[i]) V.pop_back();
		if(szz(V)) {
			int d = V.back().Se - i - 1;
			if(d) {
				ans[1][d] = min(ans[1][d], i + 1);
			}
		}
	}
	for(int i=N-1;i;i--) ans[1][i] = min(ans[1][i], ans[1][i+1]);
	for(int i=1;i<=N;i++) {
		int val = min(ans[0][i] - i, ans[1][i]);
		if(val == N + 1 - i) val = -1;
		printf("%d ",val);
	} puts("");
	return 0;
}

Compilation message (stderr)

box.cpp: In function 'int main()':
box.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
box.cpp:37:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", H+i);
                        ~~~~~^~~~~~~~~~~

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