ACM-ICPC 2018 徐州赛区网络预赛

队伍人不齐打这场真心累啊…

BE, GE or NE

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000 + 10;

int f[maxn][210];
int a[maxn], b[maxn], c[maxn];
int n, m, k, l;

int main()
{
	scanf("%d%d%d%d", &n, &m, &k, &l);
	for (int i = 1; i <= n; i++)
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	for (int i = 0; i <= l + 100; i++)
		f[n + 1][i] = -1;
	for (int i = l + 101; i < k + 100; i++)
		f[n + 1][i] = 0;
	for (int i = k + 100; i <= 200; i++)
		f[n + 1][i] = 1;
	for (int i = n; i >= 1; i--)
	{
		//  for (int w=90;w<110;w++) printf("%d",f[i+1][w]);
		// printf("\n");
		for (int j = 0; j <= 200; j++)
		{

			int x = -1, y = -1, z = -1;
			if (a[i])
			{
				x = j + a[i];
				if (x > 200)
					x = 200;
			}
			if (b[i])
			{
				y = j - b[i];
				if (y < 0)
					y = 0;
			}
			if (c[i])
				z = 200 - j;
			if (i & 1)
			{
				if ((x >= 0) && (f[i + 1][x] == 1))
				{
					f[i][j] = 1;
					continue;
				}
				if ((y >= 0) && (f[i + 1][y] == 1))
				{
					f[i][j] = 1;
					continue;
				}
				if ((z >= 0) && (f[i + 1][z] == 1))
				{
					f[i][j] = 1;
					continue;
				}
				if (((x < 0) || ((x >= 0) && (f[i + 1][x] == -1))) && ((y < 0) || ((y >= 0) && (f[i + 1][y] == -1))) && ((z < 0) || ((z >= 0) && (f[i + 1][z] == -1))))
				{
					f[i][j] = -1;
					continue;
				}
				f[i][j] = 0;
			}
			else
			{
				if ((x >= 0) && (f[i + 1][x] == -1))
				{
					f[i][j] = -1;
					continue;
				}
				if ((y >= 0) && (f[i + 1][y] == -1))
				{
					f[i][j] = -1;
					continue;
				}
				if ((z >= 0) && (f[i + 1][z] == -1))
				{
					f[i][j] = -1;
					continue;
				}
				if (((x < 0) || ((x >= 0) && (f[i + 1][x] == 1))) && ((y < 0) || ((y >= 0) && (f[i + 1][y] == 1))) && ((z < 0) || ((z >= 0) && (f[i + 1][z] == 1))))
				{
					f[i][j] = 1;
					continue;
				}
				f[i][j] = 0;
			}
		}
	}
	if (f[1][m + 100] == 1)
		printf("Good Ending");
	else if (f[1][m + 100] == 0)
		printf("Normal Ending");
	else
		printf("Bad Ending");
}

Features Track

#include <cstdio>
#include <unordered_map>
using namespace std;
int t, n;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		unordered_map<int, unordered_map<int, pair<int, int>>> mp;
		int ans = 0;
		for (int i = 1, k, x, y; i <= n; ++i)
			for (scanf("%d", &k); k--;)
			{
				scanf("%d%d", &x, &y);
				pair<int, int> &p = mp[x][y];
				if (p.first == i)
					continue; //坑
				if (p.first != i - 1)
					p.second = 0;
				p.first = i, ans = max(ans, ++p.second);
			}
		if (ans == 1)
			ans = 0; //坑
		printf("%d\n", ans);
	}
}

Trace

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 200000 + 10;

struct node
{
	int l, r, mx;
} t[maxn * 4];

int n;
long long ans;
int x[maxn], y[maxn], tmp1[maxn], tmp2[maxn];

void build(int cur, int l, int r)
{
	t[cur].l = l;
	t[cur].r = r;
	t[cur].mx = 0;
	if (l == r)
		return;
	int mid = (l + r) / 2;
	build(cur * 2, l, mid);
	build(cur * 2 + 1, mid + 1, r);
}

void update(int cur, int l, int r, int v)
{
	if ((t[cur].l == l) && (t[cur].r == r))
	{
		t[cur].mx = max(t[cur].mx, v);
		return;
	}
	t[cur * 2].mx = max(t[cur * 2].mx, t[cur].mx);
	t[cur * 2 + 1].mx = max(t[cur * 2 + 1].mx, t[cur].mx);
	t[cur].mx = 0;
	int mid = (t[cur].l + t[cur].r) / 2;
	if (r <= mid)
		update(cur * 2, l, r, v);
	else if (l > mid)
		update(cur * 2 + 1, l, r, v);
	else
		update(cur * 2, l, mid, v), update(cur * 2 + 1, mid + 1, r, v);
}

int query(int cur, int pos)
{
	if (t[cur].l == t[cur].r)
		return t[cur].mx;
	t[cur * 2].mx = max(t[cur * 2].mx, t[cur].mx);
	t[cur * 2 + 1].mx = max(t[cur * 2 + 1].mx, t[cur].mx);
	t[cur].mx = 0;
	int mid = (t[cur].l + t[cur].r) / 2;
	if (pos <= mid)
		return query(cur * 2, pos);
	else
		return query(cur * 2 + 1, pos);
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &x[i], &y[i]);
	for (int i = 1; i <= n; i++)
		tmp1[i] = x[i];
	sort(tmp1 + 1, tmp1 + n + 1);
	for (int i = 1; i <= n; i++)
		x[i] = lower_bound(tmp1 + 1, tmp1 + n + 1, x[i]) - tmp1;
	for (int i = 1; i <= n; i++)
		tmp2[i] = y[i];
	sort(tmp2 + 1, tmp2 + n + 1);
	for (int i = 1; i <= n; i++)
		y[i] = lower_bound(tmp2 + 1, tmp2 + n + 1, y[i]) - tmp2;
	ans = 0;
	build(1, 1, n);
	for (int i = n; i >= 1; i--)
	{
		int k = query(1, y[i]);
		ans += tmp1[x[i]] - tmp1[k];
		update(1, 1, y[i], x[i]);
	}
	build(1, 1, n);
	for (int i = n; i >= 1; i--)
	{
		int k = query(1, x[i]);
		ans += tmp2[y[i]] - tmp2[k];
		update(1, 1, x[i], y[i]);
	}
	printf("%lld", ans);
	return 0;
}

Ryuji doesn’t want to study

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct SegmentTree
{
	struct Node
	{
		ll set, sum, ans;
	};
	vector<Node> v;
	int LAST, L, R;
	SegmentTree(int n) : LAST(n), v(2 * n + 1) {}
	void build(ll a[], int l, int r)
	{
		if (l < r)
		{
			int m = l + (r - l) / 2;
			build(a, l, m), build(a, m + 1, r);
			lv(l, r).set = INF;
		}
		else
			lv(l, r).set = a[l];
		maintain(l, r);
	}
	Node &lv(int l, int r)
	{
		return v[l + r | l != r];
	}
	void push_down(Node &lc, Node &rc, Node &fa)
	{
		if (fa.set != INF)
			lc.set = rc.set = fa.set, fa.set = INF;
	}
	void push_up(const Node &lc, const Node &rc, Node &fa, int l, int r, int m)
	{
		fa.sum = lc.sum + rc.sum;
		fa.ans = lc.ans + rc.ans + lc.sum * (r - m);
	}
	void maintain(int l, int r)
	{
		if (l < r)
		{
			int m = l + (r - l) / 2;
			push_up(lv(l, m), lv(m + 1, r), lv(l, r), l, r, m);
		}
		if (lv(l, r).set != INF)
		{
			int len = r - l + 1;
			lv(l, r).sum = len * lv(l, r).set;
			lv(l, r).ans = (1LL + len) * len / 2 * lv(l, r).set;
		}
	}
	Node ask(int l, int r, ll val = 0, bool out = 1)
	{
		if (out)
			return L = l, R = r, ask(1, LAST, val, 0);
		if (lv(l, r).set != INF)
		{
			int len = min(R, r) - max(l, L) + 1;
			v[0].sum = len * lv(l, r).set;
			v[0].ans = (1LL + len) * len / 2 * lv(l, r).set;
		}
		else if (L <= l && r <= R)
			v[0] = lv(l, r);
		else
		{
			int m = l + (r - l) / 2;
			if (R <= m)
				return ask(l, m, val, 0);
			if (L > m)
				return ask(m + 1, r, val, 0);
			push_up(ask(l, m, val, 0), ask(m + 1, r, val, 0), v[0], max(L, l), min(R, r), m);
		}
		return v[0];
	}
	void set(int l, int r, ll val, bool out = 1)
	{
		if (out)
			return L = l, R = r, set(1, LAST, val, 0);
		if (L <= l && r <= R)
			lv(l, r).set = val;
		else
		{
			int m = l + (r - l) / 2;
			push_down(lv(l, m), lv(m + 1, r), lv(l, r));
			if (L <= m)
				set(l, m, val, 0);
			else
				maintain(l, m);
			if (R > m)
				set(m + 1, r, val, 0);
			else
				maintain(m + 1, r);
		}
		maintain(l, r);
	}
};
ll n, q, a[100009];
int main()
{
	scanf("%lld%lld", &n, &q);
	for (ll i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);
	SegmentTree tree(n);
	tree.build(a, 1, n);
	for (ll i = 0, a, b, c; i < q; ++i)
	{
		scanf("%lld%lld%lld", &a, &b, &c);
		if (a == 1)
			printf("%lld\n", tree.ask(b, c).ans);
		if (a == 2)
			tree.set(b, b, c);
	}
}

Characters with Hash

#include <cstdio>
using namespace std;
char s[1000009], z[9];
int t, n, ans;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%s%s", &n, z, s);
		for (int i = ans = 0, tmp, flag = 0; i < n; ++i)
		{
			if (tmp = (int)z[0] - (int)s[i], tmp < 0)
				tmp = -tmp;
			if (flag)
				ans += 2;
			else if (tmp)
				for (flag = 1; tmp; tmp /= 10)
					++ans;
		}
		if (ans == 0)
			ans = 1; //坑
		printf("%d\n", ans);
	}
}