Submission #299485

#	Time	Username	Problem	Language	Result	Execution time	Memory
299485		user202729	Seats (IOI18_seats)	C++17	100 / 100	2380 ms	118136 KiB

seats

#include "seats.h"
#include<vector>
#include<climits>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>

struct Tree{
	struct T{
		int minimum, count;
		T operator+(int lazy) const{return {minimum+lazy, count};}
		T operator+(T other) const{
			if(minimum<other.minimum) return *this;
			if(minimum>other.minimum) return other;
			return {minimum, count+other.count};
		}
	};
	struct Node{
		int lazy;
		T data_;
		T data() const{return data_+lazy;}
	};
	std::vector<Node> data;
	Tree(){}
	Tree(int number): data(number*2, {0, {0, 1}}){}
	// note: initial state is inconsistent (counts values of nonleafs are 1)

	void add(int left, int right, int value){
		if(left==right) return;
		assert(left<right);

		left+=int(data.size()/2); right+=int(data.size()/2);
		std::array<int, 2> const old{{left, right-1}};
		for(; left<right; left>>=1, right>>=1){
			if(left&1) data[left++].lazy+=value;
			if(right&1) data[--right].lazy+=value;
		}
		for(auto it: old){
			for(it>>=1; it; it>>=1){
				data[it].data_=data[it*2].data()+data[it*2+1].data();
			}
		}
	}

	/* // not necessary (...)
	void get(int left, int right){
		assert(left<right);
		left+=int(data.size()/2); right+=int(data.size()/2);
		for(auto it: {left, right-1}){
			for(int shift=31^__builtin_clz(it); shift; --shift){
				auto const node=it>>shift;
				if(auto const l=data[node].lazy){
					data[node].lazy=0;
					data[node].data_.minimum+=l;
					data[node*2].lazy+=l;
					data[node*2+1].lazy+=l;
				}
			}
		}

		T result{};
	}
	*/

	int get(){
		// operator+ is commutative
		auto const d=data[1].data();
		assert(d.minimum>=4);
		return d.minimum==4 ? d.count: 0;
	}
};

struct MyData{
	MyData(){}

	//int width;
	std::vector<std::vector<int>> value; // pos -> time (in 0..H*W), with padded (H*W) values
	struct Pos{ int row, col; };
	std::vector<Pos> pos; // time -> pos
	Tree tree;

	template<int factor> void addTree(Pos minimum){
		auto const [r, c]=minimum;
		std::array<int, 4> times{{
			value[r][c],
			value[r+1][c],
			value[r][c+1],
			value[r+1][c+1],
		}};
		std::sort(begin(times), end(times));

		tree.add(times[0], times[1], factor);
		tree.add(times[2], times[3], factor*5); // 5 is always greater than 4 => impossible
	}

	MyData(int const H, int const W, std::vector<int> const& R_, std::vector<int> const& C_):
		value(H+2, std::vector<int>(W+2, H*W)),
		pos(H*W), tree(H*W)
	{
		for(int time=0; time<H*W; ++time){
			pos[time]={R_[time], C_[time]};
			value[R_[time]+1][C_[time]+1]=time;
		}

		for(int i=0; i<(int)value.size()-1; ++i)
			for(int j=0; j<(int)value[0].size()-1; ++j)
				addTree<1>({i, j});
	}

	int swap(int first, int sec){
		std::swap(pos[first], pos[sec]);

		std::array<std::array<int, 2> /* can be Pos too if it has comparison operators */, 8> minimums{{
			{pos[first].row, pos[first].col},
			{pos[first].row, pos[first].col+1},
			{pos[first].row+1, pos[first].col},
			{pos[first].row+1, pos[first].col+1},
			{pos[sec].row, pos[sec].col},
			{pos[sec].row, pos[sec].col+1},
			{pos[sec].row+1, pos[sec].col},
			{pos[sec].row+1, pos[sec].col+1},
		}};
		std::sort(begin(minimums), end(minimums));
		auto const last=std::unique(begin(minimums), end(minimums));

		std::for_each(minimums.begin(), last, [&](auto it){ addTree<-1>({it[0], it[1]}); });

		value[pos[first].row+1][pos[first].col+1]=first;
		value[pos[sec].row+1][pos[sec].col+1]=sec;

		std::for_each(minimums.begin(), last, [&](auto it){ addTree<1>({it[0], it[1]}); });

		return tree.get();
	}
} myData;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	myData=MyData{H, W, std::move(R), std::move(C)};
}

int swap_seats(int a, int b) {
	return myData.swap(a, b);
}

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