Submission #291281

#	Time	Username	Problem	Language	Result	Execution time	Memory
291281		user202729	Seats (IOI18_seats)	C++17	37 / 100	4102 ms	149848 KiB

seats

// moreflags=grader.cpp
// 6
// perhaps this is not the correct solution.
// only recomputing changed block might speed it up by 2x but...
#include "seats.h"
#include<vector>
#include<climits>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>

struct MyData{
	static int constexpr blockSize=
#if LOCAL
		7
#else
		2000
#endif
		;
	struct Pos{int row, col;};
	struct Rectangle{Pos minimum, maximum;
		Rectangle& operator+=(Rectangle other){ // compute the union of two rectangles.
			minimum.row=std::min(minimum.row, other.minimum.row);
			minimum.col=std::min(minimum.col, other.minimum.col);
			maximum.row=std::max(maximum.row, other.maximum.row);
			maximum.col=std::max(maximum.col, other.maximum.col);
			return *this;
		}
		Rectangle operator+(Rectangle other) const{return other+=*this;}

		Rectangle intersectUnchecked(Rectangle other) const{
			Rectangle const result={
				{
					std::max(minimum.row, other.minimum.row),
					std::max(minimum.col, other.minimum.col)
				},
				{
					std::min(maximum.row, other.maximum.row),
					std::min(maximum.col, other.maximum.col)
				}
			};
			return result;
		}
		bool valid() const{ // note that rectangles with zero area are still valid.
			return maximum.row>=minimum.row and maximum.col>=minimum.col;
		}
		int area() const{ // compute the area of the rectangle, obviously.
			// should not overflow because HW<=1000000.
			assert(valid());
			return (maximum.row-minimum.row)*(maximum.col-minimum.col);
		}

		bool contains(Rectangle other) const{
			return
				minimum.row<=other.minimum.row and
				minimum.col<=other.minimum.col and
				maximum.row>=other.maximum.row and
				maximum.col>=other.maximum.col;
		}

		static Rectangle from(Pos it){return Rectangle{it, {it.row+1, it.col+1}};}
	};

	struct Cover{Rectangle bound; int missing; // contains the information of a sequence of positions of consecutive numbers.
		int count() const{ // obviously correct.
			assert(missing<=bound.area());
			return bound.area()-missing;
		};
		Cover operator+(Cover other) const{ // merge two covers. Must be called with valid and consecutive blocks.
			auto const resultBound=bound+other.bound;
			auto const resultMissing=resultBound.area()-count()-other.count();
			assert(resultMissing>=0);
			return {resultBound, resultMissing};
		}
	};

	struct Max2D{ // dynamic structure to quickly answer maximum query of a 2D rectangle.
		std::vector<std::vector<int>> data;
		Max2D(int numRow=0, int numCol=0): data(numRow*2, std::vector<int>(numCol*2)){}
		int get(int first, int sec, int third, int forth)const{ // (minX, maxX, minY, maxY) -> maximum. O(log(n) log(m)).
			// ranges are half-inclusive, as usual.
			assert(first<sec); assert(third<forth);
			first+=int(data.size()/2); sec+=int(data.size()/2);
			third+=int(data[0].size()/2); forth+=int(data[0].size()/2);

			int result=INT_MIN;

			auto const process=[&](int nodeIndex){ // Only modifies result.
				auto const& node=data[nodeIndex]; // node in first dimension.
				for(int first=third, sec=forth; first<sec; first>>=1, sec>>=1){
					if(first&1) result=std::max(result, node[first++]);
					if(sec&1) result=std::max(result, node[--sec]);
				}
			};

			for(;first<sec; first>>=1, sec>>=1){
				if(first&1) process(first++);
				if(sec&1) process(--sec);
			}
			return result;
		}
		int get(int first, int sec)const{ // (x, y). O(1).
			first+=int(data.size()/2);
			sec+=int(data[0].size()/2);
			return data[first][sec];
		}
		void set(int first, int sec, int value){ // set a cell. O(log(n) log(m)).
			first+=int(data.size()/2);
			sec+=int(data[0].size()/2);
			data[first][sec]=value;

			for(int third=first; third>>=1;)
				data[third][sec]=std::max(data[third*2][sec], data[third*2+1][sec]);

			for(int third=first; third; third>>=1)
				for(int forth=sec; forth>>=1;)
					data[third][forth]=std::max(data[third][forth*2], data[third][forth*2+1]);
		}
	};

	struct Block{
		struct T{Cover cover; int index;};
		struct MinInfo{ // struct to maintain minimum information of a multiset of numbers.
			int count, value;
			/*
			MinInfo operator+(int other)const{ // add a number to the set.
				if(value<other) return *this;
				if(value>other) return {1, other};
				return {count+1, value};
			}
			*/
			MinInfo operator+(MinInfo other)const{ // get minimum information of the union of two multisets.
				// commutative
				if(value<other.value) return *this;
				if(value>other.value) return other;
				return {count+other.count, value};
			}

			bool operator==(MinInfo other) const{
				return count==other.count and value==other.value;
			}
		};
		//std::vector<MinInfo> suffix;

		std::vector<T> cover; // union of prefixes of items, and their last index (inclusive right, might be 0)
		std::array<Pos, blockSize> items;
		std::vector<MinInfo> tree; // minimum info of missing values
		int base; // offset of the indices represented in maximum (used in `get` function)
		//Max2D const* maximum; // it's really dangerous to store raw pointers.
		// Very hard to debug (might seg fault at arbitrary location) and very easy to get wrong (rule of three, rule of five, rule of zero)

		MinInfo getTree(int left, int right) const{ // get minimum info of missing values in a range
			auto const oldLeft=left, oldRight=right;

			MinInfo result{0, INT_MAX};
			left+=int(tree.size()/2); right+=int(tree.size()/2);
			for(;left<right; left>>=1, right>>=1){
				if(left&1) result=result+tree[left++];
				if(right&1) result=result+tree[--right];
			}

			assert(([&]{
				MinInfo naive{0, INT_MAX};
				for(int index=oldLeft; index<oldRight; ++index){
					naive=naive+tree[index+int(tree.size()/2)];
					assert((tree[index+int(tree.size()/2)]==MinInfo{1, cover[index].cover.missing}));
				}
				assert(naive==result);
				return true;
			}()));
			return result;
		}

		int number;
		void build(){ // recompute necessary information after items changes
			assert(number<=blockSize);
			assert(number!=0);
			cover.clear();
			cover.push_back({{Rectangle::from(items[0]), 0}, 0});
			for(int index=1; index<number; ++index){
				auto& [curCover, curCoverIndex]=cover.back();
				auto& [prevBound, prevMissing]=curCover;
				auto const next=Rectangle::from(items[index])+prevBound;
				auto const diff=next.area()-prevBound.area();
				assert(diff>=0);
				if(diff==0){ // curCover is not needed, replace it
					assert(prevMissing>0);
					--prevMissing;
					++curCoverIndex;
					assert(curCoverIndex==index);
				}else{ // make a new cover entry
					cover.push_back({{next, prevMissing+diff-1}, index});
				}
			}
			// done computing cover

			/*
			suffix.resize(cover.size());
			suffix.back()={1, cover.back().cover.missing};
			for(int pos=(int)cover.size()-1; pos--;)
				suffix[pos]=suffix[pos+1]+cover[pos].cover.missing;
				*/

			// rebuild tree (O(cover.size()), amortized (not including destruction cost))
			tree.resize(cover.size()*2);
			for(int index=0; index<(int)cover.size(); ++index)
				tree[cover.size()+index]={1, cover[index].cover.missing};
			for(auto index=(int)cover.size(); --index;)
				tree[index]=tree[index*2]+tree[index*2+1];
		}
		void setWithoutBuild(int index, Pos pos){ // no comment needed
			assert(index<number);
			items[index]=pos;
		}
		int get_(Cover const previous, Max2D const& maximum)const{ // number of merges from previous to a full rectangle, excluding previous itself and including merging all in the current block
			// it's obvious that only cover needs to be considered

			auto const countNaive=[&](int left, int right){
				int result{};
				for(int pos1=left; pos1<right; ++pos1)
					result+=(previous+cover[pos1].cover).missing==0;
				return result;
			};
			// return countNaive(0,(int)cover.size()); // <-- alternative explanation
			// // note that "0" here means the first element of cover, which contains at least one item from (items)

			int result=0;
			int pos=0;
			auto const invariantCheck=[&]{
				assert(result==countNaive(0, pos));
			};
			invariantCheck();

			auto const lastCoverIndexSatisfy=[&](int pos, auto condition){
				for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
					if(pos+step<(int)cover.size() and condition(pos+step))
						pos+=step;
				return pos;
			};

			// these 3 advance functions will do nothing if pos reached (int)cover.size().

			auto const advanceUnion=[&]{
				// advance pos to first that covers the whole of the union area (target)
				// will not change result.
				assert(pos>=0);
				if(pos==(int)cover.size()) return;
				auto const oldPos=pos;
				auto const target=cover[pos].cover.bound+previous.bound;

				auto const value=maximum.get(target.minimum.row, target.maximum.row, target.minimum.col, target.maximum.col)-base;
				assert(cover[pos].index<=value);

				pos=lastCoverIndexSatisfy(pos-1, [&](int pos){ return cover[pos].index<value; })+1;
				if(pos!=(int)cover.size()){
					assert(cover[pos].index>=value);
					assert(cover[pos].cover.count()+previous.count()>=target.area());
				}

				assert(pos>=oldPos);
				assert(countNaive(oldPos, pos)==0);
				invariantCheck();
			};

			auto const advanceOnce=[&]{
				assert(pos>=0);
				if(pos==(int)cover.size()) return;
				result+=countNaive(pos, pos+1);
				++pos;
				invariantCheck();
			};

			auto const advanceSameIntersect=[&](int next){ // process the set with the same intersect (note that
				// having the same intersect(ion) is a necessary but not sufficient condition)
				assert(pos>=0);
				if(pos==(int)cover.size()) return;

				int const oldPos=pos;
				auto const curIntersect=cover[pos].cover.bound.intersectUnchecked(previous.bound);
				assert(curIntersect.valid());
				pos=next;
				assert(pos>=0); assert(pos<=(int)cover.size());
				assert(pos>=oldPos);

				auto const [minCount, minMissing]=getTree(oldPos, pos);
				assert(minMissing>=curIntersect.area()-previous.missing);
				int curResult=0;
				if(minMissing==curIntersect.area()-previous.missing) curResult=minCount;
				result+=curResult;

				assert(([&]{
					auto const naive=countNaive(oldPos, pos);
					assert(naive==curResult);
					return true;
				}()));

				assert(pos>=oldPos);
				if(pos!=(int)cover.size())
					assert(cover[pos].cover.bound.intersectUnchecked(previous.bound).area()>curIntersect.area());
				invariantCheck();
			};

			advanceUnion();
			advanceOnce();
			if(pos==(int)cover.size()) return result;
			assert(not previous.bound.contains(cover[pos].cover.bound));

			advanceUnion();
			if(pos==(int)cover.size()) return result;
			if(not cover[pos].cover.bound.contains(previous.bound)){
				// cover[pos].cover.bound must extrude from `previous` in exactly one direction.
				auto const countExceed=[&](int pos)->int{
					return
							(cover[pos].cover.bound.minimum.row<previous.bound.minimum.row)+
							(cover[pos].cover.bound.minimum.col<previous.bound.minimum.col)+
							(cover[pos].cover.bound.maximum.row>previous.bound.maximum.row)+
							(cover[pos].cover.bound.maximum.col>previous.bound.maximum.col);
				};
				assert(countExceed(pos)==1);
				int next=lastCoverIndexSatisfy(pos, [&](int pos){ return countExceed(pos)==1; });
				advanceSameIntersect(next+1);
				// now all covers with index >= pos and extrude in exactly one direction are processed.

				if(pos==(int)cover.size()) return result;
				assert(countExceed(pos)>=2);
			}
			assert(cover[pos].cover.bound.contains(previous.bound));

			advanceSameIntersect((int)cover.size());
			assert(pos==(int)cover.size());
			return result;
		}
		std::pair<int, Cover> get(Cover const previous, Max2D const& maximum)const{
			return {get_(previous, maximum), previous+cover.back().cover};
		}
	};

	int number;
	std::vector<Block> data;
	Max2D maximum;
	MyData(){}
	MyData(int const H, int const W, std::vector<int> const& R, std::vector<int> const& C):
		number(H*W), data((number-1)/blockSize+1), maximum(H, W)
	{
		assert(number!=0);
		for(auto& it: data) it.number=blockSize;
		data.back().number-=(int)data.size()*blockSize-number;
		assert((int)R.size()==number); assert((int)C.size()==number);

		for(int blockIndex=0; blockIndex<(int)data.size(); ++blockIndex)
			for(int indexInBlock=0; indexInBlock<data[blockIndex].number; ++indexInBlock){
				auto const index=blockIndex*blockSize+indexInBlock;
				auto const row=R[index], col=C[index];
				data[blockIndex].items[indexInBlock]={row, col};
				assert(maximum.get(row, col)==0);
				maximum.set(row, col, index);
			}

		for(int index=0; index<(int)data.size(); ++index){
			//data[index].maximum=&maximum;
			data[index].base=index*blockSize;
			buildAt(index);
		}
	}

	void buildAt(int index){
		data[index].build(
				//index*blockSize, maximum
				);
	}

	int getResult() const{
		Cover current{Rectangle::from(data[0].items[0]), 1};
		int result{};
		for(auto const& it: data){
			auto [count, next]=it.get(current, maximum);
			result+=count; current=next;
		}
		assert(current.missing==0);
		if(result<=0){
			assert(std::cerr<<"result="<<result<<'\n');
			assert(false);
		}
		return result;
	}

	Pos get(int index) const{
		assert(0<=index); assert(index<number);
		return data[index/blockSize].items[index%blockSize];
	}

	int swap(int first, int sec){
		auto const x=get(first), y=get(sec);
		data[first/blockSize].setWithoutBuild(first%blockSize, y);
		data[sec/blockSize].setWithoutBuild(sec%blockSize, x);

		assert(maximum.get(x.row, x.col)==first);
		assert(maximum.get(y.row, y.col)==sec);
		maximum.set(x.row, x.col, sec);
		maximum.set(y.row, y.col, first);

		buildAt(first/blockSize);
		if(first/blockSize!=sec/blockSize)
			buildAt(sec/blockSize);

		return getResult();
	}

} myData;

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

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

Compilation message (stderr)

seats.cpp: In member function 'MyData::Block::MinInfo MyData::Block::getTree(int, int) const':
seats.cpp:157:15: warning: unused variable 'oldLeft' [-Wunused-variable]
  157 |    auto const oldLeft=left, oldRight=right;
      |               ^~~~~~~
seats.cpp:157:29: warning: unused variable 'oldRight' [-Wunused-variable]
  157 |    auto const oldLeft=left, oldRight=right;
      |                             ^~~~~~~~
seats.cpp: In lambda function:
seats.cpp:252:16: warning: unused variable 'oldPos' [-Wunused-variable]
  252 |     auto const oldPos=pos;
      |                ^~~~~~

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