// 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
Main.cpp:10:9: fatal error: BITSum.h: No such file or directory
10 | #include"BITSum.h"
| ^~~~~~~~~~
compilation terminated.
