Codeforces Round #576 (Div. 2)

http://codeforces.com/contest/1199

A、City Day

左边X个比他大，右边Y个比他大的左边的数字

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
	int n, x, y;
	scanf("%d%d%d", &n, &x, &y);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++)
	{
		bool f = true;
		for (int j = max(1, i - x); j <= min(n, i + y); j++)
		{
			if (a[j] < a[i])
			{
				f = false;
				break;
			}
		}
		if (f == true)
		{
			printf("%d", i);
			return 0;
		}
	}
}

B、Water Lily

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
	double a, b;
	scanf("%lf%lf", &a, &b);
	double ans = (a * a + b * b) / 2 / a;
	printf("%.10lf", ans - a);
}

C、MP3

先找出能容纳的数字个数，再枚举左端点，算代价。

#include <bits/stdc++.h>
#define Pair pair<int,int>
#define ll long long
using namespace std;
const int MAXN = 4e5 + 5;
Pair que[MAXN];
map<int, int>mp;
ll sum[MAXN];
int a, cnt;
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	ll ans = 1e18;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		if (mp[a])
			que[mp[a]].second++;
		else
		{
			mp[a] = ++cnt;
			que[mp[a]].first = a;
			que[mp[a]].second = que[mp[a]].second + 1;
		}
	}
	int wei = m * 8 / n;
	if (wei >= 19)
	{
		printf("0");
		return 0;
	}
	int news = 1 << wei;
	if (cnt <= news)
		printf("0");
	else
	{
		sort(que + 1, que + cnt + 1, [](Pair q, Pair w) {
			return q.first < w.first;
		});
		for (int i = 1; i <= cnt; i++)
			sum[i] = sum[i - 1] + que[i].second;
		for (int i = 1; i + news - 1 <= cnt; i++)
			ans = min(sum[i - 1] - sum[0] + sum[cnt] - sum[i + news - 1], ans);
		printf("%lld", ans);
	}
}

D、Wlefare State

N个数字，两种操作，操作一单点赋值，操作二将区间所有小于val的数都变成val，由于只需要在最后输出每个点的值，所以考虑直接线段树打标记，每次操作一下传标记。

（其实下面代码的update1可以直接换成给que[1]打标记）

#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 2e5 + 5;
struct node
{
	int l;
	int r;
	int minn;
	int mark;
}que[MAXN * 4];
int n, m, ql, qr;
int a[MAXN];
int val;
void up(int k)
{
	que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark = max(que[k].mark,que[k<<1].mark);
		que[k << 1 | 1].mark = max(que[k].mark, que[k << 1 | 1].mark);
		que[k << 1].minn = max(que[k << 1].minn, que[k].mark);
		que[k << 1 | 1].minn = max(que[k << 1 | 1].minn, que[k].mark);
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
	{
		que[k].minn = a[left];
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update1(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = max(que[k].mark, val);
		que[k].minn = max(que[k].minn, val);
		return;
	}
	down(k);
	imid;
	update1(lson);
	update1(rson);
	up(k);
}
void update2(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].minn = val;
		return;
	}
	down(k);
	imid;
	update2(lson);
	update2(rson);
	up(k);
}
int query(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].minn;
	down(k);
	imid;
	return query(lson) + query(rson);
}
int main()
{
	int op;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	build();
	scanf("%d", &m);
	while (m--)
	{
		scanf("%d", &op);
		if (op == 1)
		{
			scanf("%d", &ql);
			qr = ql;
			scanf("%d", &val);
			update2();
		}
		else
		{
			scanf("%d", &val);
			ql = 1, qr = n;
			update1();
		}
	}
	for (int i = 1; i <= n; i++)
	{
		ql = i; qr = i;
		printf("%d%c", query(), i == n ? '\n' : ' ');
	}
}