Submission #497983

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
497983	2021-12-24T07:48:09 Z	user202729	Loop Town (CCO21_day2problem3)	C++17	25 / 25	1406 ms	51712 KB

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	312 KB	Output is correct
3	Correct	4 ms	580 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	4 ms	592 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	4 ms	572 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	312 KB	Output is correct
3	Correct	4 ms	580 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	4 ms	592 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	4 ms	572 KB	Output is correct
9	Correct	85 ms	5712 KB	Output is correct
10	Correct	85 ms	5672 KB	Output is correct
11	Correct	93 ms	5716 KB	Output is correct
12	Correct	87 ms	5672 KB	Output is correct
13	Correct	83 ms	5676 KB	Output is correct
14	Correct	92 ms	5668 KB	Output is correct
15	Correct	76 ms	5712 KB	Output is correct
16	Correct	85 ms	5684 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	312 KB	Output is correct
3	Correct	4 ms	580 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	4 ms	592 KB	Output is correct
6	Correct	4 ms	592 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	4 ms	572 KB	Output is correct
9	Correct	85 ms	5712 KB	Output is correct
10	Correct	85 ms	5672 KB	Output is correct
11	Correct	93 ms	5716 KB	Output is correct
12	Correct	87 ms	5672 KB	Output is correct
13	Correct	83 ms	5676 KB	Output is correct
14	Correct	92 ms	5668 KB	Output is correct
15	Correct	76 ms	5712 KB	Output is correct
16	Correct	85 ms	5684 KB	Output is correct
17	Correct	1348 ms	51532 KB	Output is correct
18	Correct	1354 ms	51572 KB	Output is correct
19	Correct	1347 ms	51500 KB	Output is correct
20	Correct	1351 ms	51528 KB	Output is correct
21	Correct	1328 ms	51524 KB	Output is correct
22	Correct	1406 ms	51656 KB	Output is correct
23	Correct	1343 ms	51712 KB	Output is correct
24	Correct	1135 ms	51488 KB	Output is correct
25	Correct	1006 ms	51488 KB	Output is correct
26	Correct	1120 ms	51528 KB	Output is correct
27	Correct	0 ms	204 KB	Output is correct
28	Correct	1 ms	204 KB	Output is correct