Submission #1115071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115071		Math4Life2020	Furniture (JOI20_furniture)	C++17	100 / 100	1715 ms	312236 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = (1LL<<20); const ll E = 20;
ll st[2*Nm];
ll v2(ll x) {
	return __builtin_ctz(x);
}
ll qry(ll x) { //sum of elements with indices 0,1,2,3,...,x
	if (x<0) {
		return 0;
	}
	ll l = v2(x+1);
	return (st[(x>>l)+(1LL<<(E-l))]+qry(x-(1LL<<l)));
}
void upd(ll a, ll v) {
	ll p = a+Nm;
	while (p>0) {
		st[p]+=v;
		p=p/2;
	}
}

struct hashPii {
	size_t operator()(const pii &p) const { return p.first+ (1000005) * p.second; }
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,M; cin >> N >> M;
	bool C[N][M];
	for (ll n=0;n<N;n++) {
		for (ll m=0;m<M;m++) {
			cin >> C[n][m];
		}
	}
	//represent a point (i,j) as M*i+j
	ll fdeg[N*M]; ll rdeg[N*M];
	vector<ll> fadj[N*M]; vector<ll> radj[N*M];
	vector<pii> vedge;
	for (ll x=0;x<(N*M);x++) {
		fdeg[x]=0;
		rdeg[x]=0;
	}
	unordered_set<pii,hashPii> edges;
	for (ll n=0;n<N;n++) {
		for (ll m=0;m<M;m++) {
			if (m != (M-1)) {
				if (!C[n][m] && !C[n][m+1]) {
					vedge.push_back({M*n+m,M*n+m+1});
					fadj[M*n+m].push_back(M*n+m+1);
					fdeg[M*n+m]++;
					radj[M*n+m+1].push_back(M*n+m);
					rdeg[M*n+m+1]++;
					edges.insert({M*n+m,M*n+m+1});
				}
			}
			if (n != (N-1)) {
				if (!C[n][m] && !C[n+1][m]) {
					vedge.push_back({M*n+m,M*n+m+M});
					fadj[M*n+m].push_back(M*n+m+M);
					fdeg[M*n+m]++;
					radj[M*n+m+M].push_back(M*n+m);
					rdeg[M*n+m+M]++;
					edges.insert({M*n+m,M*n+m+M});
				}
			}
		}
	}
	for (pii p0: vedge) {
		ll a = p0.first; ll b = p0.second;
		upd(a+1,1);
		upd(b,-1);
	}
	fdeg[N*M-1]++; rdeg[0]++;
	//auto square = [](int x) -> long long { return (long long)x * x; };
	queue<ll> vq;
	auto wp = [&](ll x, ll y) -> void {
		if (edges.find({x,y})==edges.end()) {
			return;
		}
		edges.erase(edges.find({x,y}));
		upd(x+1,-1);
		upd(y,1);
		fdeg[x]--;
		rdeg[y]--;
		vq.push(x);
		vq.push(y);
	};
	auto prc = [&]() -> void {
		while (!vq.empty()) {
			ll x = vq.front(); vq.pop();
			if (x==(N*M-1) || (x==0)) {
				continue;
			}
			ll a = x/M; ll b = x%M;
			if (rdeg[x]==0 && fdeg[x]!=0) {
				if (a!=(N-1)) {
					wp(x,x+M);
				}
				if (b != (M-1)) {
					wp(x,x+1);
				}
			}
			if (rdeg[x]!=0 && fdeg[x]==0) {
				// wp(x-M,x);
				// wp(x-1,x);
				if (a != 0) {
					wp(x-M,x);
				}
				if (b != 0) {
					wp(x-1,x);
				}
			}
			if (rdeg[x]==0 && fdeg[x]==0) {
				if (a!=(N-1)) {
					wp(x,x+M);
				}
				if (b != (M-1)) {
					wp(x,x+1);
				}
				if (a != 0) {
					wp(x-M,x);
				}
				if (b != 0) {
					wp(x-1,x);
				}
			}
		}
	};
	for (ll p=0;p<(N*M);p++) {
		vq.push(p);
	}
	prc();
	ll Q; cin >> Q;
	for (ll q=0;q<Q;q++) {
		ll x,y; cin >> x >> y; x--; y--;
		ll p = x*M+y;
		if (qry(p)==0) {
			cout << "0\n";
		} else {
			rdeg[p]=0; fdeg[p]=0;
			vq.push(p);
			prc();
			cout << "1\n";
		}
	}
}

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