Submission #299618

#	Time	Username	Problem	Language	Result	Execution time	Memory
299618		square1001	Seats (IOI18_seats)	C++14	17 / 100	4027 ms	44780 KiB

seats

#include "seats.h"
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class segment_tree {
private:
	static const int inf = 1012345678;
	int sz; bool ismax;
	vector<int> val;
public:
	segment_tree() : sz(0), ismax(false), val() {};
	segment_tree(int N, const string& type_) : ismax(type_ == "max") {
		sz = 1;
		while(sz < N) sz *= 2;
		val = vector<int>(sz * 2, ismax ? -inf : inf);
	}
	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, sum; vector<int> X, Y, sxl, sxr, syl, syr, flag;
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.resize(H * W);
	sxr.resize(H * W);
	syl.resize(H * W);
	syr.resize(H * W);
	sxl[0] = X[0]; sxr[0] = X[0]; syl[0] = Y[0]; syr[0] = Y[0];
	for(int i = 1; i < H * W; ++i) {
		sxl[i] = min(sxl[i - 1], X[i]);
		sxr[i] = max(sxr[i - 1], X[i]);
		syl[i] = min(syl[i - 1], Y[i]);
		syr[i] = max(syr[i - 1], Y[i]);
	}
	sum = 0;
	flag.resize(H * W);
	for(int i = 0; i < H * W; ++i) {
		int d = (sxr[i] - sxl[i] + 1) * (syr[i] - syl[i] + 1);
		flag[i] = (d == i + 1 ? 1 : 0);
		sum += flag[i];
	}
}
int swap_seats(int va, int vb) {
	if(va > vb) swap(va, vb);
	swap(X[va], X[vb]);
	swap(Y[va], Y[vb]);
	if(va == 0) {
		sxl[0] = X[0]; sxr[0] = X[0]; syl[0] = Y[0]; syr[0] = Y[0];
	}
	for(int i = max(va, 1); i < vb; ++i) {
		sxl[i] = min(sxl[i - 1], X[i]);
		sxr[i] = max(sxr[i - 1], X[i]);
		syl[i] = min(syl[i - 1], Y[i]);
		syr[i] = max(syr[i - 1], Y[i]);
	}
	for(int i = va; i < vb; ++i) {
		int d = (sxr[i] - sxl[i] + 1) * (syr[i] - syl[i] + 1);
		sum -= flag[i];
		flag[i] = (d == i + 1 ? 1 : 0);
		sum += flag[i];
	}
	return sum;
}

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