#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#ifndef LOCAL/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize "unroll-loops"
#pragma GCC target "mmx,sse,sse2,sse3,sse4,avx,avx2,fma,abm,popcnt,tune=native" //*/
//#pragma GCC optimize "prefetch-loop-arrays"
#endif // LOCAL
using namespace std; using namespace __gnu_pbds;
#define foru(i,a,b) for(ll i=(a);i<(b);i++)
#define ford(i,a,b) for(ll i=(a)-1;i>=(b);i--)
#define fori(a,b) foru(i,a,b)
#define forj(a,b) foru(j,a,b)
#define fork(a,b) foru(k,a,b)
#define seto(x,i) memset(x,i,sizeof x)
#define pf first
#define ps second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp make_pair
#define mt make_tuple
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __builtin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define P2(x) (1LL<<(x))
#define sz(x) (ll)x.size()
#define all(x) begin(x),end(x)
#define lwb lower_bound
#define upb upper_bound
#if __SIZEOF_INT128__
typedef __int128_t i128; typedef __uint128_t ui128;
#endif
typedef int64_t ll; typedef uint64_t ull; typedef long double lld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<lld,lld> pdd;
template<class T1,class T2> using ordered_map=tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>; template<class T1> using ordered_set=ordered_map<T1,null_type>;
template<class T> using minpq=std::priority_queue<T,vector<T>,greater<T>>; template<class T> using maxpq=std::priority_queue<T,vector<T>,less<T>>;
template<class T> using minpairingheap=__gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>; template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>;
const int inf=0x3f3f3f3f,MOD=1e9+7; const ll INF=0x3f3f3f3f3f3f3f3f; const lld PI=acos((lld)-1);
const ll SEED=443214^chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
mt19937 randgen(SEED); ll rand(ll a, ll b){return uniform_int_distribution<ll>(a,b)(randgen);}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll fpow(ll a,ll b){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%MOD;a=a*a%MOD;}return ret;} ll fpow(ll a,ll b,ll M){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%M;a=a*a%M;}return ret;}
template<class T1,class T2>constexpr const auto _min(const T1&x,const T2&y){return x<y?x:y;} template<class T,class...Ts>constexpr auto _min(const T&x,const Ts&...xs){return _min(x,_min(xs...));}
template<class T1,class T2>constexpr const auto _max(const T1&x,const T2&y){return x>y?x:y;} template<class T,class...Ts>constexpr auto _max(const T&x,const Ts&...xs){return _max(x,_max(xs...));}
#define min(...) _min(__VA_ARGS__)
#define max(...) _max(__VA_ARGS__)
template<class T1,class T2>constexpr bool ckmin(T1&x,const T2&y){return x>y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmin(T&x,const Ts&...xs){return ckmin(x,min(xs...));}
template<class T1,class T2>constexpr bool ckmax(T1&x,const T2&y){return x<y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmax(T&x,const Ts&...xs){return ckmax(x,max(xs...));}
template<class T1,class T2,class T3,class T4> constexpr const auto operator+(const pair<T1,T2>& a,const pair<T3,T4>& b){return mp(a.pf+b.pf,a.ps+b.ps);}
template<class T1,class T2,class T3,class T4> constexpr const auto operator-(const pair<T1,T2>& a,const pair<T3,T4>& b){return mp(a.pf-b.pf,a.ps-b.ps);}
template<class T1,class T2,class T3> constexpr const auto operator *(const pair<T1,T2>& a,const T3& b){return mp(a.pf*b,a.ps*b);}
template<class T1,class T2,class T3> constexpr const auto operator *(const T1& a,const pair<T2,T3>& b){return b*a;}
template<class T1,class T2,class T3> constexpr const auto operator /(const pair<T1,T2>& a,const T3& b){return mp(a.pf/b,a.ps/b);}
template<class T1,class T2,class T3,class T4> constexpr const auto& operator+=(pair<T1,T2> &a,const pair<T3,T4> &b){return a=a+b;}
template<class T1,class T2,class T3,class T4> constexpr const auto& operator-=(pair<T1,T2> &a,const pair<T3,T4> &b){return a=a-b;}
template<class T1,class T2,class T3> constexpr const auto& operator*=(pair<T1,T2> &a,const T3 &b){return a=a*b;}
template<class T1,class T2,class T3> constexpr const auto& operator/=(pair<T1,T2> &a,const T3 &b){return a=a/b;}
template<class T,class U> void erase(T& t,const U& u){auto it=t.find(u);if(it!=end(t)) t.erase(it);}
template<class T> T pop(queue<T> &a){auto b=a.front(); a.pop(); return b;} template<class T> auto pop(T &a){auto b=a.top(); a.pop(); return b;}
template<class T> T operator -(vector<T> &a,size_t x){return a[a.size()-x];} template<class T> T operator -(deque<T> &a,size_t x){return a[a.size()-x];}
struct chash{
static ll splitmix64(ll x){x+=0x9e3779b97f4a7c15; x=(x^(x>>30))*0xbf58476d1ce4e5b9; x=(x^(x>>27))*0x94d049bb133111eb; return x^(x>>31);}
template<class T> size_t operator()(const T &x) const{return splitmix64(hash<T>()(x)+SEED);}
template<class T1,class T2> size_t operator()(const pair<T1,T2>&x)const{return 31*operator()(x.first)+operator()(x.second);}};
struct mint {//thanks benq
//static constexpr mint rt() { return RT; } // primitive root for FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint():v(0) {}
mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
bool operator==(const mint& o) const {
return v == o.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }
//friend void re(mint& a) { ll x; re(x); a = mint(x); }
//friend string ts(mint a) { return ts(a.v); }
mint& operator+=(const mint& o) {
if ((v += o.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& o) {
if ((v -= o.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& o) {
v = int((ll)v*o.v%MOD); return *this; }
mint& operator/=(const mint& o) { return (*this) *= inv(o); }
friend mint pow(mint a, ll p) {
mint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
friend mint inv(const mint& a) { assert(a.v != 0);
return pow(a,MOD-2); }
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
friend string to_string(const mint& a){ return to_string(a.v); }
friend std::ostream & operator<<(std::ostream & Str, mint const & v) {
Str << v.v;
return Str;
}
friend istream& operator>> (istream& stream, mint& v){
stream>>v.v;
return stream;
}
};
void fin(string s){freopen(s.c_str(),"r",stdin);} void fout(string s){freopen(s.c_str(),"w",stdout);} void fio(string s){fin(s+".in"); fout(s+".out");}
string to_string(char c){return string(1,c);} string to_string(char* s){return (string)s;} string to_string(string s){return s;}
template<class T> string to_string(complex<T> c){stringstream ss; ss<<c; return ss.str();}
template<class T1,class T2> string to_string(pair<T1,T2> p){return "("+to_string(p.pf)+","+to_string(p.ps)+")";}
template<class T1,class T2,class T3> string to_string(tuple<T1,T2,T3> p){auto [a,b,c]=p; return "("+to_string(a)+","+to_string(b)+","+to_string(c)+")";}
template<class T1,class T2,class T3,class T4> string to_string(tuple<T1,T2,T3,T4> p){auto [a,b,c,d]=p; return "("+to_string(a)+","+to_string(b)+","+to_string(c)+","+to_string(d)+")";}
template<class T> string to_string(T v){string ret="{"; for(const auto& x:v) ret+=to_string(x)+","; return ret+"}";}
void DBG(){cerr<<"]"<<endl;} template<class T,class... Ts> void DBG(T x,Ts... xs){cerr<<to_string(x); if(sizeof...(xs)) cerr<<", "; DBG(xs...);}
#ifdef LOCAL
#define dbg(...) cerr<<"Line("<< __LINE__<<") -> ["<<#__VA_ARGS__<<"]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
#define nl "\n"
const int N=2e6+10,M=0;
struct BITree{
ll bit[N];
void upd(int x,int v){
for(ckmin(++x,N);x<N;x+=x&-x) bit[x]+=v;
}
ll query(int x){
ll ret=0;
if(x<0){
return 0;
}
for(ckmin(++x,N-1);x;x-=x&-x) ret+=bit[x];
return ret;
}
ll query(int l,int r){
return query(r)-query(l-1);
}
} b1,b2;
ll n,aa[N],ab[N],p[N],v1[N],v2[N],v3[N],v4[N],v5[N],val[N],ans,t,t2;
vector<ll> xs,ys;
void input(){
cin>>n>>t;
fori(0,n){
cin>>aa[i]>>ab[i];
}
}
void solve(){
input();
fori(0,n){
xs.pb(aa[i]); ys.pb(ab[i]);
}
sort(all(xs)); sort(all(ys));
fori(0,n){
p[lwb(all(xs),aa[i])-begin(xs)]=lwb(all(ys),ab[i])-begin(ys);
}
fori(0,n){
if(p[i]<i){
p[i]+=n;
}
}
fori(0,n){
v1[i]=b1.query(p[i]-n,p[i]);
v2[i]+=b1.query(p[i],inf);
v3[i]+=b1.query(-inf,p[i]-n);
b1.upd(p[i],1);
t2+=i-v1[i];
}
ford(i,n,0){
v2[i]+=b2.query(p[i]+n,inf);
v3[i]+=b2.query(p[i]);//same as p[i]-n,p[i]
v4[i]=b2.query(p[i],p[i]+n);
b2.upd(p[i],1);
}
fori(0,n){
val[i]=v2[i]-v1[i]-v4[i]-v3[i]*3;
}
sort(val,val+n); reverse(val,val+n);
t=0;
fori(0,n){
t+=val[i];
ckmax(ans,t+i*(i+1));
}
ans=-ans;
ans+=t2;
cout<<ans<<nl;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
fin("a.txt");
#endif
int T=1; //cin>>T;
//n=5;
//iota(aa,aa+n,0);
//iota(ab,ab+n,0);
foru(t,1,T+1){
//random_shuffle(ab,ab+n);
solve();
//ll x=tt.solve();
//cout<<x<<nl;
}
return 0;
}
/**
*/
Compilation message
Main.cpp: In function 'void fin(std::string)':
Main.cpp:117:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | void fin(string s){freopen(s.c_str(),"r",stdin);} void fout(string s){freopen(s.c_str(),"w",stdout);} void fio(string s){fin(s+".in"); fout(s+".out");}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void fout(std::string)':
Main.cpp:117:78: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | void fin(string s){freopen(s.c_str(),"r",stdin);} void fout(string s){freopen(s.c_str(),"w",stdout);} void fio(string s){fin(s+".in"); fout(s+".out");}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 4 |
Correct |
6 ms |
25308 KB |
Output is correct |
| 5 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 6 |
Correct |
6 ms |
25324 KB |
Output is correct |
| 7 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 8 |
Correct |
6 ms |
25432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 4 |
Correct |
6 ms |
25308 KB |
Output is correct |
| 5 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 6 |
Correct |
6 ms |
25324 KB |
Output is correct |
| 7 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 8 |
Correct |
6 ms |
25432 KB |
Output is correct |
| 9 |
Correct |
83 ms |
37228 KB |
Output is correct |
| 10 |
Correct |
85 ms |
37300 KB |
Output is correct |
| 11 |
Correct |
83 ms |
37304 KB |
Output is correct |
| 12 |
Correct |
83 ms |
37248 KB |
Output is correct |
| 13 |
Correct |
87 ms |
37376 KB |
Output is correct |
| 14 |
Correct |
72 ms |
36028 KB |
Output is correct |
| 15 |
Correct |
75 ms |
36284 KB |
Output is correct |
| 16 |
Correct |
80 ms |
36152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 4 |
Correct |
6 ms |
25308 KB |
Output is correct |
| 5 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 6 |
Correct |
6 ms |
25324 KB |
Output is correct |
| 7 |
Correct |
6 ms |
25436 KB |
Output is correct |
| 8 |
Correct |
6 ms |
25432 KB |
Output is correct |
| 9 |
Correct |
83 ms |
37228 KB |
Output is correct |
| 10 |
Correct |
85 ms |
37300 KB |
Output is correct |
| 11 |
Correct |
83 ms |
37304 KB |
Output is correct |
| 12 |
Correct |
83 ms |
37248 KB |
Output is correct |
| 13 |
Correct |
87 ms |
37376 KB |
Output is correct |
| 14 |
Correct |
72 ms |
36028 KB |
Output is correct |
| 15 |
Correct |
75 ms |
36284 KB |
Output is correct |
| 16 |
Correct |
80 ms |
36152 KB |
Output is correct |
| 17 |
Correct |
1057 ms |
144188 KB |
Output is correct |
| 18 |
Correct |
1018 ms |
144204 KB |
Output is correct |
| 19 |
Correct |
1020 ms |
144160 KB |
Output is correct |
| 20 |
Correct |
1018 ms |
144096 KB |
Output is correct |
| 21 |
Correct |
1014 ms |
144180 KB |
Output is correct |
| 22 |
Correct |
1022 ms |
144308 KB |
Output is correct |
| 23 |
Correct |
1020 ms |
144272 KB |
Output is correct |
| 24 |
Correct |
900 ms |
129676 KB |
Output is correct |
| 25 |
Correct |
905 ms |
131488 KB |
Output is correct |
| 26 |
Correct |
915 ms |
129700 KB |
Output is correct |
| 27 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 28 |
Correct |
3 ms |
24924 KB |
Output is correct |
