# 最高的牛Tallest Cow（前缀和）- POJ 3263

Description

FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow.

FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17.

For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

Input

Line 1: Four space-separated integers: N, I, H and R

Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B.

Output

Lines 1..N: Line i contains the maximum possible height of cow i.

Sample Input

9 3 5 5

1 3

5 3

4 3

3 7

9 8

Sample Output

5

4

5

3

4

4

5

5

5

```#include<iostream>
#include<cstdio>
#include<map>
#include<utility>
using namespace std;

const int maxn = 10005;
int n, I, h, r;
int c[maxn], d[maxn];
map<pair<int, int>, bool>existed;

int main()
{
cin >> n >> I >> h >> r;
for (int i = 0; i < r; i++)
{
int a, b;
scanf("%d%d", &a, &b);
if (a > b)  swap(a, b);
if (existed[make_pair(a, b)])   continue;
//map判断一下是否曾经操作过了
d[a + 1]--, d[b]++;
existed[make_pair(a, b)] = true;
}

for (int i = 1; i <= n; i++)
{
c[i] = c[i - 1] + d[i];
printf("%d\n", h + c[i]);
}
return 0;
}```

197 篇文章30 人订阅

0 条评论

## 相关文章

### 当函数成为一等公民时，设计模式的变化

GOF提出的设计模式，其本质思想是封装变化。故而，创建型模式封装的是对象创建的变化，结构型模式封装的是对象之间的协作与组合结构，行为型模式则封装了对象行为的变化...

3105

42411

1598

4035

3596

3755

2028

1074

1052

3319