Submission #497983

#	Time	Username	Problem	Language	Result	Execution time	Memory
497983		user202729	Loop Town (CCO21_day2problem3)	C++17	25 / 25	1406 ms	51712 KiB

Main

// https://oj.uz/problem/statistics/CCO21_day2problem3

// not proven.
// Prove by AC or disprove by WA

#if not LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
// { ==== Begin library BITSum.h ====

template<class T>
struct Tree{
	std::vector<T> data;
	Tree(int number=0): data(number){}
	void reset(int number){data.clear(); data.resize(number);}

	template<bool strict=true>
	T sumSuffix(int index)const{
		if(strict){
			assert(0<=index); assert(index<=(int)data.size());
		}
		T result{};
		while(index<(int)data.size()){
			result+=data[index];
			index|=index+1;
		}
		return result;
	}
	T sum(int left, int right) const{
		assert(0<=left); assert(left<=right); assert(right<=(int)data.size());
		return sumSuffix(left)-sumSuffix(right);
	}

	template<bool strict=true>
	void add(int index, T delta){
		if(strict){
			assert(0<=index); assert(index<(int)data.size());
		}
		++index;
		while(index>0){
			data[index-1]+=delta;
			index&=index-1;
		}
	}
};

// } ==== End library BITSum.h ====
int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int number; std::cin>>number;
	int _; std::cin>>_;
	std::vector<int> a(number), b(number);
	for(int index=0; index<number; ++index)
		std::cin>>a[index]>>b[index];

	// compress values
	for(auto p:{&a,&b}){
		auto& vector=*p;
		auto values=vector;
		std::sort(begin(values), end(values));
		for(auto& x: vector) x=
			int(std::lower_bound(begin(values), end(values), x)-begin(values));
	}

	// permute such that a is identity permutation
	{
		std::vector<int> b1(number);
		for(int index=0; index<number; ++index)
			b1[a[index]]=b[index];
		b=std::move(b1);
		a.clear();
	}
	// no need to store a anymore
	
	auto tree=Tree<int>(number*3);
	int64_t curValue {}; // number of good pairs (do not cross). Should be maximized
	struct Item{
		int delta, index;
		bool operator<(Item other) const{return delta>other.delta;}// queue top is minimum delta
	};
	std::priority_queue<Item> queue;
	for(int index=0; index<number; ++index){
		if(b[index]<index) b[index]+=number;
		curValue+=tree.sum(std::max(b[index]-number, 0), b[index]);
		queue.push({b[index]-index, index});
		tree.add(b[index], 1);
	}

	auto bestValue=curValue;
	
	for(int _=0; _<number; ++_){
		auto [delta, index]=queue.top(); queue.pop();
		assert(b[index]-index==delta);
		assert(tree.sum(b[index], b[index]+1)==1);
		tree.add(b[index], -1);
		
		// with respect to the old location of the point.
		int numAfter=number-1-index;
		int goodBefore=tree.sum(0, b[index]);
		int badAfter=tree.sumSuffix(b[index]+number);
		int goodAfter=numAfter-badAfter;
		int good=goodBefore+goodAfter;

		// do the flip
		curValue-=good;
		curValue+=number-1-good;
		b[index]+=number;
		tree.add(b[index], 1);

		//... no need to add back to queue, only do one round

		// update bestValue
		bestValue=std::max(bestValue, curValue);
	}
	assert(queue.empty());

	std::cout<<(int64_t)number*(number-1)/2u-bestValue<<'\n';
}

• Subtask 1: 12 / 12
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7