Submission #291273

#	Time	Username	Problem	Language	Result	Execution time	Memory
291273		user202729	Seats (IOI18_seats)	C++17	25 / 100	4072 ms	97784 KiB

seats

// moreflags=grader.cpp
// 6
// late
// One of my worst performances so far.
// At least I decided to switch to problem 3 and got 49 points there.
// Almost everyone got 37 points for this problem...
// Figuring out the optimal solution during the contest time is good,
// but not if the optimal solution has some logical error (even if they're patchable)
// or it's too complex to implement...
//
#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
		3
#else
		1000
#endif
		;
	struct Pos{int row, col;};
	struct Rectangle{Pos minimum, maximum;
		Rectangle& operator+=(Rectangle other){
			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{
			return maximum.row>=minimum.row and maximum.col>=minimum.col;
		}
		int area() const{
			assert(valid());
			return (maximum.row-minimum.row)*(maximum.col-minimum.col);
		}

		bool contains(Rectangle other) const{return area()==(*this+other).area();}

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

	struct Cover{Rectangle bound; int missing;
		int count() const{
			assert(missing<=bound.area());
			return bound.area()-missing;
		};
		Cover operator+(Cover other) const{
			auto const resultBound=bound+other.bound;
			auto const resultMissing=resultBound.area()-count()-other.count();
			assert(resultMissing>=0);
			return {resultBound, resultMissing};
		}
	};

	struct Max2D{
		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{
			first+=int(data.size()/2); sec+=int(data.size()/2);
			third+=int(data[0].size()/2); forth+=int(data[0].size()/2);
			assert(first<sec); assert(third<forth);

			int result=INT_MIN;

			auto const process=[&](int nodeIndex){
				auto const& node=data[nodeIndex];
				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{
			first+=int(data.size()/2);
			sec+=int(data[0].size()/2);
			return data[first][sec];
		}
		void set(int first, int sec, int value){
			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;};
		std::vector<T> cover;
		struct MinInfo{
			int count, value;
			MinInfo operator+(int other)const{
				if(value<other) return *this;
				if(value>other) return {1, other};
				return {count+1, value};
			}
			MinInfo operator+(MinInfo other)const{ // commutative
				if(value<other.value) return *this;
				if(value>other.value) return other;
				return {count+other.count, value};
			}
		};
		//std::vector<MinInfo> suffix;
		std::array<Pos, blockSize> items;
		std::vector<MinInfo> tree; // minimum info of missing values
		int base;
		//Max2D const* maximum;

		MinInfo getTree(int left, int right) const{
			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)].count==1);
					assert(tree[index+int(tree.size()/2)].value==cover[index].cover.missing);
				}
				assert(naive.count==result.count);
				assert(naive.value==result.value);
				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){
					assert(prevMissing>0);
					--prevMissing;
					++curCoverIndex;
					assert(curCoverIndex==index);
				}else{
					cover.push_back({{next, prevMissing+diff-1}, index});
				}
			}

			/*
			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;
				*/

			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){
			assert(index<number);
			items[index]=pos;
		}
		int get_(Cover const previous, Max2D const& maximum)const{
			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());

			int result=0;
			int pos=0;

			auto const advanceUnion=[&]{
				// advance pos to first that covers the whole of the union area (target)
				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;
				for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
					if(pos+step<(int)cover.size() and cover[pos+step].index<value)
						pos+=step;
				assert(pos<oldPos or cover[pos].index<value);
				++pos;
				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);
			};

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

			auto const advanceSameIntersect=[&](int next){
				// process the set with the same intersect
				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());
				/*

				for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
					if(pos+step<(int)cover.size()){
						auto const tmp=cover[pos+step].cover.bound.intersectUnchecked(previous.bound);
						assert(tmp.valid());
						assert(tmp.contains(curIntersect));
						if(tmp.area()==curIntersect.area())
							pos+=step;
					}
				++pos;
				*/
				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());
			};

			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)){
				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=pos;
				for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
					if(next+step<(int)cover.size() and countExceed(next)==1)
						next+=step;
				assert(countExceed(pos)==countExceed(next));
				advanceSameIntersect(next+1);
				if(pos==(int)cover.size()) return result;
			}
			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:146:15: warning: unused variable 'oldLeft' [-Wunused-variable]
  146 |    auto const oldLeft=left, oldRight=right;
      |               ^~~~~~~
seats.cpp:146:29: warning: unused variable 'oldRight' [-Wunused-variable]
  146 |    auto const oldLeft=left, oldRight=right;
      |                             ^~~~~~~~
seats.cpp: In lambda function:
seats.cpp:224:16: warning: unused variable 'oldPos' [-Wunused-variable]
  224 |     auto const oldPos=pos;
      |                ^~~~~~

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