Submission #295266

#	Time	Username	Problem	Language	Result	Execution time	Memory
295266		Poimidorka	Furniture (JOI20_furniture)	C++14	100 / 100	2993 ms	245944 KiB

furniture

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>


using namespace std;


#define x first
#define y second


typedef long long ll;


const int maxn = 2e6 + 1;


ll func(pair<int, int> a) {
	return ((ll)a.x << 30) | a.y;
}

char mat[1001][1001];
vector<int> g[maxn / 2];
vector<int> gr[maxn / 2];
unordered_map<ll, int> num;
int beg[maxn];
int t[maxn * 4];
int pos[maxn];
int a[maxn];
char in[maxn], out[maxn];
bool used[maxn], pus[maxn];
int n, m, uk;


int to(int x, int y) {
	return m * x + y;
}


vector<int> path;
int susp[maxn * 3];
int head = 0, tail = 0;


void dfs(int v) {
	pus[v] = 1;
	for (int u : g[v])
		if (!pus[u])
			dfs(u);
	path.push_back(v);
}


void build(int v, int l, int r) {
	if (l == r - 1) {
		t[v] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}


int getmax(int v, int l, int r, int l2, int r2) {
	if (l == l2 && r == r2)
		return t[v];
	int m = (l + r) / 2;
	if (r2 <= m)
		return getmax(v * 2, l, m, l2, r2);
	if (l2 >= m)
		return getmax(v * 2 + 1, m, r, l2, r2);
	return max(getmax(v * 2, l, m, l2, m), getmax(v * 2 + 1, m, r, m, r2));
}


void upd(int v, int l, int r, int pos) {
	if (l == r - 1) {
		t[v] = -1;
		return;
	}
	int m = (l + r) / 2;
	if (pos >= m)
		upd(v * 2 + 1, m, r, pos);
	else
		upd(v * 2, l, m, pos);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}


void de(int v) {
	used[v] = 1;
	for (int u : g[v]) {
		upd(1, 0, uk, num[func({v, u})]);
		if (!used[u]) {
			in[u]--;
			if (in[u] == 0)
				susp[tail++] = u;
		}
	}
	for (int u : gr[v]) {
		upd(1, 0, uk, num[func({u, v})]);
		if (!used[u]) {
			out[u]--;
			if (out[u] == 0)
				susp[tail++] = u;
		}
	}
}


void clr() {
	while (head != tail) {
		if (!used[susp[head]])
			de(susp[head++]);
		else
			head++;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		g[i].reserve(2);
		gr[i].reserve(2);
		for (int j = 0; j < m; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == '1')
				used[to(i, j)] = 1;
		}
	}
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m; j++)
			if (mat[i][j] != '1' && mat[i - 1][j] != '1') {
				g[to(i - 1, j)].push_back(to(i, j));
				gr[to(i, j)].push_back(to(i - 1, j));
				in[to(i, j)]++;
				out[to(i - 1, j)]++;
			}
	for (int i = 0; i < n; i++)
		for (int j = 1; j < m; j++)
			if (mat[i][j] != '1' && mat[i][j - 1] != '1') {
				g[to(i, j - 1)].push_back(to(i, j));
				gr[to(i, j)].push_back(to(i, j - 1));
				in[to(i, j)]++;
				out[to(i, j - 1)]++;
			}
	used[0] = 1;
	int fn = m * (n - 1) + m - 1;
	used[fn] = 1;
	for (int i = 1; i < fn; i++) {
		if ((in[i] == 0 || out[i] == 0)) {
			susp[tail++] = i;
		}
	}
	for (int i = 0; i <= fn; i++)
		if (!pus[i])
			dfs(i);
	reverse(path.begin(), path.end());
	for (int i = 0; i < path.size(); i++)
		pos[path[i]] = i;
	for (int i = 0; i < path.size(); i++) {
		beg[path[i]] = uk;
		for (auto el : g[path[i]]) {
			num[func({path[i], el})] = uk;
			a[uk++] = pos[el];
		}
	}
	build(1, 0, uk);
	clr();
	int q;
	cin >> q;
	/*
	for (auto el : rin)
		cout << '\t' << el.x << ' ' << el.y << endl;
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << ' ';
	cout << endl;
	for (int i = 0; i < uk; i++)
		cout << a[i] << ' ';
	cout << endl;
	*/
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		int p = to(x - 1, y - 1);
		//cout << beg[p] << endl;
		if (!used[p] && getmax(1, 0, uk, 0, beg[p]) <= pos[p]) {
			cout << "0\n";
		}
		else {
			cout << "1\n";
			if (!used[p]) {
				susp[tail++] = p;
				clr();
			}
		}
	}
	return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |  for (int i = 0; i < path.size(); i++)
      |                  ~~^~~~~~~~~~~~~
furniture.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for (int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95