oj.uz

답안 #72260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72260 2018-08-26T06:28:44 Z https://blog.naver.com/nywoo19(#2158, HawkBreaker, njchung99, yu0524) 박스런 (FXCUP3_box) C++17
0 / 100
 3 ms 560 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int seg[2000000];
int a[500100],ch[500100],dap[500100];
vector<int> vt;
int getidx(int x) {
	return lower_bound(vt.begin(), vt.end(), x) - vt.begin();
}
int update(int pos, int val, int node, int x, int y)
{
	if (pos < x || pos > y)return seg[node];
	if (x == y)return seg[node] = max(val, seg[node]);
	int mid = (x + y) / 2;
	return seg[node] = max(update(pos, val, node * 2, x, mid), update(pos, val, node * 2 + 1, mid + 1, y));
}
int query(int lo, int hi, int node, int x, int y)
{
	if (hi < x || y < lo)return 0;
	if (lo <= x&&y <= hi)return seg[node];
	int mid = (x + y) / 2;
	return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		vt.push_back(a[i]);
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for (int i = 1; i <= n; i++)
		a[i] = getidx(a[i]);
	int t = vt.size();
	for (int i = 1; i <= n; i++)
	{
		if (a[i] !=t - 1)
			ch[i] = query(a[i] + 1, n - 1, 1, 0, t - 1);
		update(a[i], i, 1, 0, t - 1);
	}
	int prev = 0;
	for (int i = 2; i <= n; i++)
	{
		if (i - ch[i]-1 > prev)
		{
			for (int y = prev + 1; y <= i - ch[i]-1; y++)
				dap[y] = i - y;
			prev = i - ch[i]-1;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dap[i])
			printf("%d ", dap[i]);
		else
			printf("-1 ");
	}
}

Compilation message

box.cpp: In function 'int main()':
box.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
box.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Incorrect 2 ms 560 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Incorrect 2 ms 560 KB Output isn't correct
6 Halted 0 ms 0 KB -