Submission #286055

#	Time	Username	Problem	Language	Result	Execution time	Memory
286055		user202729	Rectangles (IOI19_rect)	C++17	72 / 100	5070 ms	831528 KiB

rect

// moreflags=grader.cpp
// 13
#include "rect.h"
#include<vector>
#include<set>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

long long count_rectangles(std::vector<std::vector<int> > a) {
	if(a.size()<3 or a[0].size()<3) return 0;


	struct T{ int right, depth; };
	using Segments=std::vector<std::vector<T>>;
	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;});
		std::set<int> done;
		for(auto [value, index]: items){
			auto const [iterator, inserted]=done.insert(index);
			assert(inserted);
			auto const next=std::next(iterator);
			if(iterator!=done.begin() and next!=done.end())
				if(auto const prevValue=*std::prev(iterator); value<data[prevValue] and value<data[*next]){
					result[prevValue+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()); // this is confusing.

		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];
				for(auto& [right, depth]: data[row][left]){
					assert(depth==1);
					auto const iterator=std::upper_bound(begin(v), end(v), right,
							[&](int right, T item){ return item.right<=right; });
					if(iterator!=v.end() and 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;}));
					}
				}
			}
		}
	};

	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){
		auto const A=(int)rows[up][left].size(), B=(int)cols[left][up].size();

		if(A*B<=((31^__builtin_clz(A+B+4)))*(A+B)){
			for(auto [right, depthDown]: rows[up][left])
			for(auto [down, depthRight]: cols[left][up])
				if(depthDown>=down-up and depthRight>=right-left)
					++result;
		}else{
			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;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:37:13: warning: unused variable 'it' [-Wunused-variable]
   37 |   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