oj.uz

답안 #497983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497983 2021-12-24T07:48:09 Z user202729 Loop Town (CCO21_day2problem3) C++17
25 / 25
 1406 ms 51712 KB 
// 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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