Submission #497982

#	Time	Username	Problem	Language	Result	Execution time	Memory
497982		user202729	Loop Town (CCO21_day2problem3)	C++17	Compilation error	0 ms	0 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>
#include"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';
}

Compilation message (stderr)

Main.cpp:10:9: fatal error: BITSum.h: No such file or directory
   10 | #include"BITSum.h"
      |         ^~~~~~~~~~
compilation terminated.