제출 #286073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286073		user202729	Rectangles (IOI19_rect)	C++17	72 / 100	5121 ms	313620 KiB

rect

// moreflags=grader.cpp
// 13
#include "rect.h"
#include<vector>
#include<set>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<climits>
 
struct T{
	int right, depth;
	T& operator=(T) && = delete;
};

struct Vector{
	struct Node{T t; int next;};
	static std::vector<Node> data;

	int node;
	int back;
	Vector(): node(-1)
			  , back(-1)
	{}
	bool empty()const{return node<0;}
	
	//struct Sentinel{};
	struct Iterator: std::iterator<std::forward_iterator_tag, T>{
		//using iterator_category=std::forward_iterator_tag;

		int node;
		Iterator(int node): node(node){} // because of the inheritance...

		//bool operator==(Sentinel) const{return node<0;}
		bool operator==(Iterator other) const{return node==other.node;}
		bool operator!=(Iterator other) const{return node!=other.node;}
		T& operator*() const{return data[node].t;} // too lazy to implement const-correctness correctly
		T* operator->() const{return &data[node].t;}
		Iterator& operator++(){ node=data[node].next; return *this; }
	};

	Iterator begin()const{ return {node}; }
	Iterator end()const{ return {-1}; }
	//Sentinel end(){ return {}; }

	void push_back(T value){
		if(node<0){
			node=back=(int)data.size();
			data.push_back({value, -1});
			return;
		}
		assert(data[back].next<0);
		back=data[back].next=(int)data.size();
		data.push_back({value, -1});
	}
	void push_front(T value){
		auto const newNode=(int)data.size();
		data.push_back({value, node});
		node=newNode;
	}
};
std::vector<Vector::Node> Vector::data; // ...

long long count_rectangles(std::vector<std::vector<int> > a) {
	using std::begin; using std::end;
	if(a.size()<3 or a[0].size()<3) return 0;
 
	struct Set{
		using Node=std::array<int, 2>;
		std::vector<Node> data;
		static Node merge(Node first, Node sec){
			return {{std::min(first[0], sec[0]), std::max(first[1], sec[1])}};
		}

		Set(int number): data(number*2, {{INT_MAX, INT_MIN}}){}
		void add(int index){
			auto node=index+(int)data.size()/2;
			data[node]={index, index};
			for(node>>=1; node; node>>=1) data[node]=merge(data[node*2], data[node*2+1]);
		}
		Node get(int first, int sec)const{
			Node result{{INT_MAX, INT_MIN}};
			first+=(int)data.size()/2;
			sec+=(int)data.size()/2;
			for(; first<sec; first>>=1, sec>>=1){
				if(first&1) result=merge(result, data[first++]);
				if(sec&1) result=merge(result, data[--sec]);
			}
			return result;
		} // good enough.
	};
 

	using Segments=std::vector<Vector>;
	auto const getSegments=[&](std::vector<int> const& data)->Segments{
		Segments result(data.size()-1); // [l] -> list of valid r in reverse sorted order
 
		struct Item{int value, index;};
		std::vector<Item> items(data.size());
		for(int index=0; index<(int)items.size(); ++index)
			items[index]={data[index], index};
		std::sort(begin(items), end(items),[&](Item first, Item sec){return first.value>sec.value;});
		Set done((int)items.size());
		for(auto [value, index]: items){
			done.add(index);
			auto const next=done.get(index+1, (int)items.size())[0];
			auto const prev=done.get(0, index)[1];
			if(prev!=INT_MIN and next!=INT_MAX){
				assert(prev<index); assert(index<next);
				if(value<data[prev] and value<data[next]){
					result[prev+1].push_back(T{next, 1});
				}
			}
		}
 
		for(auto& it: result)
			assert(std::is_sorted(begin(it), end(it), [&](T first, T sec){return first.right>sec.right;}));
 
		return result;
	};
 
	std::vector<Segments> rows(a.size()-1), cols(a[0].size()-1);
	for(int row=1; row<(int)a.size()-1; ++row)
		rows[row]=getSegments(a[row]);
	{
		std::vector<int> tmp(a.size());
		for(int col=1; col<(int)a[0].size()-1; ++col){
			std::transform(begin(a), end(a), tmp.begin(),[&](std::vector<int> const& it){return it[col];});
			cols[col]=getSegments(tmp);
		}
	}
 
	auto const computeDepth=[&](std::vector<Segments>& data)->void{
		if(data.size()<=2) return;
		assert(data[0].empty());
 
		for(int row=(int)data.size()-1; --row;){
			for(int left=0; left<(int)data[row].size(); ++left){
				auto const& v=data[row+1][left];
				if(not v.empty()){
					auto iterator=v.begin();
					for(auto& [right, depth]: data[row][left]){
						assert(depth==1);
						while(true){
							if(iterator==v.end()) goto break_outer;
							if(iterator->right<=right) break;
							++iterator;
						}
						if(iterator->right==right)
							depth=iterator->depth+1;
						else{
							assert(iterator==v.end() or iterator->right<right);
							assert(iterator==v.begin() or iterator->right>right);
							assert(std::is_sorted(begin(v), end(v), [&](T first, T sec){return first.right>sec.right;}));
						}
					}
break_outer:;
				}
			}
		}
	};
 
	computeDepth(rows);
	computeDepth(cols);
 
	struct Bit{
		std::vector<int> data;
		Bit(int number): data(number){}
		void add(int index, int value){
			for(; index>=0; index=(index&(index+1))-1)
				data[index]+=value;
		}
		int sumSuffix(int index) const{
			int result{};
			for(; index<(int)data.size(); index|=index+1)
				result+=data[index];
			return result;
		}
	};
	Bit bit((int)a[0].size()-1);
 
	enum class EventType{ add, get };
	struct Event{ EventType type; int x, y;
		bool operator<(Event other) const{return std::tie(y, type)<std::tie(other.y, other.type);}
	};
	std::vector<Event> events;
 
	int64_t result{};
	for(int up=1; up<(int)a.size()-1; ++up)
	for(int left=1; left<(int)a[0].size()-1; ++left){
		events.clear();
		for(auto [right, depthDown]: rows[up][left])
			events.push_back({EventType::get, right-left, depthDown});
		for(auto [down, depthRight]: cols[left][up])
			events.push_back({EventType::add, depthRight, down-up});
		std::sort(begin(events), end(events));
		for(auto [type, x, y]: events)
			if(type==EventType::add){
				bit.add(x, 1);
			}else{
				result+=bit.sumSuffix(x);
			}
		for(auto [type, x, y]: events)
			if(type==EventType::add){
				bit.add(x, -1);
			}
	}
	return result;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In lambda function:
rect.cpp:118:13: warning: unused variable 'it' [-Wunused-variable]
  118 |   for(auto& it: result)
      |             ^~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28