Submission #299535

#	Time	Username	Problem	Language	Result	Execution time	Memory
299535		square1001	Seats (IOI18_seats)	C++14	0 / 100	679 ms	65000 KiB

seats

#include "seats.h"
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
class segment_tree {
private:
	const int inf = 1012345678;
	int sz; bool ismax;
	vector<int> val;
public:
	segment_tree() : sz(0), ismax(false), val() {};
	segment_tree(int N, string type_) {
		if(type_ == "min") ismax = false;
		if(type_ == "max") ismax = true;
		assert(type_ == "min" || type_ == "max");
		sz = 1;
		while(sz < N) sz *= 2;
		val = vector<int>(sz * 2, ismax ? -inf : inf);
	}
	segment_tree& operator=(const segment_tree& s) {
		sz = s.sz;
		ismax = s.ismax;
		val = s.val;
		return *this;
	}
	void update(int pos, int x) {
		pos += sz;
		val[pos] = x;
		while(pos > 1) {
			pos >>= 1;
			val[pos] = (ismax ? max(val[pos * 2], val[pos * 2 + 1]) : min(val[pos * 2], val[pos * 2 + 1]));
		}
	}
	int range_query(int l, int r) {
		l += sz; r += sz;
		int ans = (ismax ? -inf : inf);
		while(l != r) {
			if(l & 1) ans = (ismax ? max(ans, val[l]) : min(ans, val[l])), ++l;
			if(r & 1) --r, ans = (ismax ? max(ans, val[r]) : min(ans, val[r]));
			l >>= 1; r >>= 1;
		}
		return ans;
	}
};
int H, W; vector<int> X, Y;
segment_tree sxl, sxr, syl, syr;
void give_initial_chart(int H_, int W_, std::vector<int> X_, std::vector<int> Y_) {
	H = H_; W = W_; X = X_; Y = Y_;
	sxl = segment_tree(H * W, "min");
	sxr = segment_tree(H * W, "max");
	syl = segment_tree(H * W, "min");
	syr = segment_tree(H * W, "max");
	for(int i = 0; i < H * W; ++i) {
		sxl.update(i, X[i]);
		sxr.update(i, X[i]);
		syl.update(i, Y[i]);
		syr.update(i, Y[i]);
	}
}
int swap_seats(int va, int vb) {
	swap(X[va], X[vb]);
	swap(Y[va], Y[vb]);
	sxl.update(va, X[va]);
	sxr.update(va, X[va]);
	syl.update(va, Y[va]);
	syr.update(va, Y[va]);
	sxl.update(vb, X[vb]);
	sxr.update(vb, X[vb]);
	syl.update(vb, Y[vb]);
	syr.update(vb, Y[vb]);
	int xl = X[0], xr = X[0] + 1, yl = Y[0], yr = Y[0] + 1, ans = 1;
	while((xr - xl) * (yr - yl) != H * W) {
		int xd = xr - xl, yd = yr - yl;
		xl = min(xl, X[xd * yd]);
		xr = max(xr, X[xd * yd] + 1);
		yl = min(yl, Y[xd * yd]);
		yr = max(yr, Y[xd * yd] + 1);
		xd = xr - xl, yd = yr - yl;
		xl = sxl.range_query(0, xd * yd);
		xr = sxr.range_query(0, xd * yd) + 1;
		yl = syl.range_query(0, xd * yd);
		yr = syr.range_query(0, xd * yd) + 1;
		if((xr - xl) * (yr - yl) == xd * yd) {
			++ans;
		}
	}
	return ans;
}

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