Codeforces Beta Round #75 (Div. 1 Only)---B.Queue
9104 단어 데이터 구조codeforces
The i-th walrus becomes displeased if there’s a younger walrus standing in front of him, that is, if exists such j (i aj. The displeasure of the i-th walrus is equal to the number of walruses between him and the furthest walrus ahead of him, which is younger than the i-th one. That is, the further that young walrus stands from him, the stronger the displeasure is.
The airport manager asked you to count for each of n walruses in the queue his displeasure. Input
The first line contains an integer n (2 ≤ n ≤ 105) — the number of walruses in the queue. The second line contains integers ai (1 ≤ ai ≤ 109).
Note that some walruses can have the same age but for the displeasure to emerge the walrus that is closer to the head of the queue needs to be strictly younger than the other one. Output
Print n numbers: if the i-th walrus is pleased with everything, print “-1” (without the quotes). Otherwise, print the i-th walrus’s displeasure: the number of other walruses that stand between him and the furthest from him younger walrus. Sample test(s) Input
6 10 8 5 3 50 45
Output
2 1 0 -1 0 -1
Input
7 10 4 6 3 2 8 15
Output
4 2 1 0 -1 -1 -1
Input
5 10 3 1 10 11
Output
1 0 -1 -1 -1
사실은 모든 i 에 대해 가장 먼 j, a [j] < a [i] 라인 트 리 를 구하 면 됩 니 다.
/*************************************************************************
> File Name: CF-75-B.cpp
> Author: ALex
> Mail: [email protected]
> Created Time: 2015 03 24 19 53 02
************************************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
const int N = 100100;
int arr[N];
int ans[N];
struct node
{
int l, r, val;
}tree[N << 2];
void build(int p, int l, int r)
{
tree[p].l = l;
tree[p].r = r;
if (l == r)
{
tree[p].val = arr[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
tree[p].val = min(tree[p << 1].val, tree[p << 1 | 1].val);
}
int query(int p, int l, int r, int lim)
{
if (tree[p].l == tree[p].r)
{
return tree[p].val < lim ? tree[p].l : -1;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (l > mid && tree[p << 1 | 1].val < lim)
{
int j = query(p << 1 | 1, l, r, lim);
if (j != -1)
{
return j;
}
}
if (r <= mid && tree[p << 1].val < lim)
{
int j = query(p << 1, l, r, lim);
if (j != -1)
{
return j;
}
}
if (l <= mid && r > mid && tree[p << 1 | 1].val < lim)
{
int j = query(p << 1 | 1, mid + 1, r, lim);
if (j != -1)
{
return j;
}
}
if (l <= mid && r > mid && tree[p << 1].val < lim)
{
int j = query(p << 1, l, mid, lim);
if (j != -1)
{
return j;
}
}
return -1;
}
int main()
{
int n;
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &arr[i]);
}
build(1, 1, n);
for (int i = 1; i < n; ++i)
{
int j = query(1, i + 1, n, arr[i]);
if (j == -1)
{
ans[i] = -1;
}
else
{
ans[i] = j - i - 1;
}
}
ans[n] = -1;
printf("%d", ans[1]);
for (int i = 2; i <= n; ++i)
{
printf(" %d", ans[i]);
}
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.