Submission #96624

#	Time	Username	Problem	Language	Result	Execution time	Memory
96624		diamond_duke	Seats (IOI18_seats)	C++11	100 / 100	2844 ms	119636 KiB

seats

#include "seats.h"
#include <algorithm>
#include <utility>
constexpr int dx[] = { -1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int seg[4000005], cnt[4000005], lazy[4000005], n, m;
std::vector<std::pair<int, int> > pos;
std::vector<std::vector<int> > arr;
inline bool in_grid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
inline void paint(int u, int x) { seg[u] += x; lazy[u] += x; }
void build(int u, int l, int r)
{
	cnt[u] = r - l + 1;
	if (l == r)
		return;
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int L, int R, int x)
{
	if (L > R)
		return;
	if (L <= l && r <= R)
	{
		paint(u, x);
		return;
	}
	if (lazy[u])
	{
		paint(u << 1, lazy[u]);
		paint(u << 1 | 1, lazy[u]);
		lazy[u] = 0;
	}
	int mid = l + r >> 1;
	if (L <= mid)
		modify(u << 1, l, mid, L, R, x);
	if (mid < R)
		modify(u << 1 | 1, mid + 1, r, L, R, x);
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]);
	cnt[u] = 0;
	if (seg[u] == seg[u << 1])
		cnt[u] += cnt[u << 1];
	if (seg[u] == seg[u << 1 | 1])
		cnt[u] += cnt[u << 1 | 1];
}
inline void modify(int x, int y, int coef)
{
	int lim = n * m;
	for (int i = 0; i < 2; i++)
	{
		int xx = x + dx[i], yy = y + dy[i];
		if (in_grid(xx, yy))
			lim = std::min(lim, arr[xx][yy]);
	}
	modify(1, 0, n * m - 1, arr[x][y], lim - 1, coef);
	std::vector<int> adj;
	for (int i = 0; i < 4; i++)
	{
		int xx = x + dx[i], yy = y + dy[i];
		if (in_grid(xx, yy))
			adj.push_back(arr[xx][yy]);
	}
	std::sort(adj.begin(), adj.end());
	if (adj.size() > 1)
		modify(1, 0, n * m - 1, adj[1], arr[x][y] - 1, coef);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
	n = H;
	m = W;
	arr.resize(n, std::vector<int>(m));
	for (int i = 0; i < R.size(); i++)
	{
		arr[R[i]][C[i]] = i;
		pos.emplace_back(R[i], C[i]);
	}
	build(1, 0, n * m - 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			modify(i, j, 1);
	}
}
int swap_seats(int a, int b)
{
	std::vector<std::pair<int, int> > vec;
	auto add = [&] (int x, int y)
	{
		vec.emplace_back(x, y);
		for (int i = 0; i < 4; i++)
		{
			int xx = x + dx[i], yy = y + dy[i];
			if (in_grid(xx, yy))
				vec.emplace_back(xx, yy);
		}
	};
	add(pos[a].first, pos[a].second);
	add(pos[b].first, pos[b].second);
	std::sort(vec.begin(), vec.end());
	vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
	for (auto &it : vec)
		modify(it.first, it.second, -1);
	std::swap(pos[a], pos[b]);
	arr[pos[a].first][pos[a].second] = a;
	arr[pos[b].first][pos[b].second] = b;
	for (auto &it : vec)
		modify(it.first, it.second, 1);
	return seg[1] == 1 ? cnt[1] : 0;
}

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
seats.cpp: In function 'void modify(int, int, int, int, int, int)':
seats.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < R.size(); i++)
                  ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30