Compare text

Find the difference between two text files

Real-time editor

Hide unchanged lines

Disable line wrap

Layout

Diff precision

Syntax highlighting

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Untitled diff

Created 2 years agoDiff never expires

1 removal

Lines
Total
Removed

Characters
Total
Removed

To continue using this feature, upgrade to Diffchecker Pro View Pricing

371 lines

1 addition

Lines
Total
Added

Characters
Total
Added

To continue using this feature, upgrade to Diffchecker Pro View Pricing

371 lines

Compete against Yourself.

Author - Aryan (@aryanc403)

Credits -

Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)

Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder

https://codeforces.com/contest/4/submission/150120627

#include <algorithm>

#include <cassert>

#include <functional>

#include <vector>

#ifdef _MSC_VER

#include <intrin.h>

#endif

#if __cplusplus >= 202002L

#include <bit>

#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {

unsigned int x = 1;

while (x < (unsigned int)(n)) x *= 2;

return x;

}

#endif

int countr_zero(unsigned int n) {

#ifdef _MSC_VER

unsigned long index;

_BitScanForward(&index, n);

return index;

#else

return __builtin_ctz(n);

#endif

}

constexpr int countr_zero_constexpr(unsigned int n) {

int x = 0;

while (!(n & (1 << x))) x++;

return x;

}

} // namespace internal

} // namespace atcoder

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {

static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,

"op must work as S(S, S)");

static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,

"e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

public:

segtree() : segtree(0) {}

explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}

explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {

size = (int)internal::bit_ceil((unsigned int)(_n));

log = internal::countr_zero((unsigned int)size);

d = std::vector<S>(2 * size, e());

for (int i = 0; i < _n; i++) d[size + i] = v[i];

for (int i = size - 1; i >= 1; i--) {

update(i);

}

void set(int p, S x) {

assert(0 <= p && p < _n);

p += size;

d[p] = x;

for (int i = 1; i <= log; i++) update(p >> i);

}

S get(int p) const {

assert(0 <= p && p < _n);

return d[p + size];

}

S prod(int l, int r) const {

assert(0 <= l && l <= r && r <= _n);

S sml = e(), smr = e();

l += size;

r += size;

while (l < r) {

if (l & 1) sml = op(sml, d[l++]);

if (r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod() const { return d[1]; }

template <bool (*f)(S)> int max_right(int l) const {

return max_right(l, [](S x) { return f(x); });

}

template <class F> int max_right(int l, F f) const {

assert(0 <= l && l <= _n);

assert(f(e()));

if (l == _n) return _n;

l += size;

S sm = e();

do {

while (l % 2 == 0) l >>= 1;

if (!f(op(sm, d[l]))) {

while (l < size) {

l = (2 * l);

if (f(op(sm, d[l]))) {

sm = op(sm, d[l]);

l++;

}

return l - size;

}

sm = op(sm, d[l]);

l++;

} while ((l & -l) != l);

return _n;

}

template <bool (*f)(S)> int min_left(int r) const {

return min_left(r, [](S x) { return f(x); });

}

template <class F> int min_left(int r, F f) const {

assert(0 <= r && r <= _n);

assert(f(e()));

if (r == 0) return 0;

r += size;

S sm = e();

do {

r--;

while (r > 1 && (r % 2)) r >>= 1;

if (!f(op(d[r], sm))) {

while (r < size) {

r = (2 * r + 1);

if (f(op(d[r], sm))) {

sm = op(d[r], sm);

r--;

}

return r + 1 - size;

}

sm = op(d[r], sm);

} while ((r & -r) != r);

return 0;

}

private:

int _n, size, log;

std::vector<S> d;

void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }

};

} // namespace atcoder

#ifdef ARYANC403

#include <header.h>

#else

#pragma GCC optimize ("Ofast")

// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#pragma GCC target ("sse,sse2,mmx")

#pragma GCC optimize ("-ffloat-store")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

#define dbg(args...) 42;

#define endl "\n"

#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801

// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html

template<class Fun> class y_combinator_result {

Fun fun_;

public:

template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }

};

template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;

#define fo(i,n) for(i=0;i<(n);++i)

#define repA(i,j,n) for(i=(j);i<=(n);++i)

#define repD(i,j,n) for(i=(j);i>=(n);--i)

#define all(x) begin(x), end(x)

#define sz(x) ((lli)(x).size())

#define eb emplace_back

#define X first

#define Y second

using lli = long long int;

using mytype = long double;

using ii = pair<lli,lli>;

using vii = vector<ii>;

using vi = vector<lli>;

template <class T>

using ordered_set = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;

// X.find_by_order(k) return kth element. 0 indexed.

// X.order_of_key(k) returns count of elements strictly less than k.

// namespace Re = std::ranges;

// namespace Ve = std::ranges::views;

const auto start_time = std::chrono::high_resolution_clock::now();

void aryanc403()

{

auto end_time = std::chrono::high_resolution_clock::now();

std::chrono::duration<double> diff = end_time-start_time;

cerr<<"Time Taken : "<<diff.count()<<"\n";

}

const lli INF = 0xFFFFFFFFFFFFFFFLL;

const lli SEED=chrono::steady_clock::now().time_since_epoch().count();

mt19937_64 rng(SEED);

inline lli rnd(lli l=0,lli r=INF)

{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP

{public:

bool operator()(ii a , ii b) //For min priority_queue .

{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};

void add( map<lli,lli> &m, lli x,lli cnt=1)

{

auto jt=m.find(x);

if(jt==m.end()) m.insert({x,cnt});

else jt->Y+=cnt;

}

void del( map<lli,lli> &m, lli x,lli cnt=1)

{

auto jt=m.find(x);

if(jt->Y<=cnt) m.erase(jt);

else jt->Y-=cnt;

}

bool cmp(const ii &a,const ii &b)

{

return a.X<b.X||(a.X==b.X&&a.Y<b.Y);

}

using S = array<lli,3>;

S op(S a, S b) { return S{a[0]+b[0],a[1]+b[1],a[2]+b[2]}; }

S e() { return S{0,0,0}; }

int target;

bool f(S v) { return v[1]<target; }

int main(void) {

ios_base::sync_with_stdio(false);cin.tie(NULL);

// freopen("txt.in", "r", stdin);

// freopen("txt.out", "w", stdout);

// cout<<std::fixed<<std::setprecision(35);

// Ve::iota(1, 6) | Ve::transform([](int x) { return x * 2; }) | Ve::reverse | Ve::take(3)

lli T=1;

cin>>T;

while(T--)

{

lli n,K;

cin>>n>>K;

vii a(n);

for(auto &x:a)

cin>>x.X;

for(auto &x:a)

cin>>x.Y;

lli ans = 0;

const lli medIdx = (n-2)/2,bigCnt = (n-1)/2+1;

vii cr={ii{-INF,-1},ii{INF,0}};

for(lli j=0;j<n;j++)

cr.eb(ii{a[j].X,j});

sort(all(cr));

const lli M = sz(cr);

atcoder::segtree<S, op, e> seg(M);

ordered_set<ii> os;

auto update=[&](const lli idx,const lli v)->void{

const lli ci = lower_bound(all(cr),ii{a[idx].X,idx})-cr.begin();

auto g = seg.get(ci);

if(a[idx].Y){

g[0]+=a[idx].X*v;

g[1]+=v;

} else {

g[2]+=v;

}

seg.set(ci,g);

};

for(lli i=0;i<n;i++){

os.insert(ii{a[i].X,i});

update(i,1);

}

auto chk=[&](const lli K,const lli med)->bool{

const lli ci = lower_bound(all(cr),ii{med,-2})-cr.begin();

const auto pd = seg.prod(ci,M);

const lli reqCnt = bigCnt - pd[1]-pd[2];

dbg(med,reqCnt);

if(reqCnt<=0)

return true;

target=reqCnt+1;

const lli lr = seg.min_left<f>(ci);

const auto pd2 = seg.prod(lr,ci);

dbg(pd2[1],pd2[0],cr[lr]);

if(pd2[1]<reqCnt)

return false;

return pd2[1]*med-pd2[0]<=K;

};

auto getMedian = [&](const lli K)->lli{

if(K==0)

return os.find_by_order(medIdx)->X;

lli l=0,r=INF;

lli l=0,r=4e9;

while(r-l>1){

const lli mid=(l+r)/2;

if(chk(K,mid))

l=mid;

else

r=mid;

}

dbg(K,l,os);

return l;

};

for(lli i=0;i<n;i++){

os.erase(ii{a[i].X,i});

update(i,-1);

if(a[i].Y==0)

ans=max(ans,a[i].X+getMedian(K));

else

ans=max(ans,a[i].X+K+getMedian(0));

os.insert(ii{a[i].X,i});

update(i,1);

}

cout<<ans<<endl;

} aryanc403();

return 0;

}

Saved diffs

Original text

Open file

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
*/
/*
  Credits -
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)
  Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder
  https://codeforces.com/contest/4/submission/150120627
*/

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

S all_prod() const { return d[1]; }

template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;

void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
    #pragma GCC target ("sse,sse2,mmx")
    #pragma GCC optimize ("-ffloat-store")
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define dbg(args...) 42;
    #define endl "\n"
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define eb emplace_back
#define X first
#define Y second

using lli = long long int;
using mytype = long double;
using ii = pair<lli,lli>;
using vii = vector<ii>;
using vi = vector<lli>;

template <class T>
using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
// X.find_by_order(k) return kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.

// namespace Re = std::ranges;
// namespace Ve = std::ranges::views;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
}

const lli INF = 0xFFFFFFFFFFFFFFFLL;
const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(SEED);
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

using S = array<lli,3>;
S op(S a, S b) { return S{a[0]+b[0],a[1]+b[1],a[2]+b[2]}; }
S e() { return S{0,0,0}; }

int target;
bool f(S v) { return v[1]<target; }

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// Ve::iota(1, 6) | Ve::transform([](int x) { return x * 2; }) | Ve::reverse | Ve::take(3)
lli T=1;
cin>>T;
while(T--)
{
    lli n,K;
    cin>>n>>K;
    vii a(n);
    for(auto &x:a)
        cin>>x.X;
    for(auto &x:a)
        cin>>x.Y;
    lli ans = 0;
    const lli medIdx = (n-2)/2,bigCnt = (n-1)/2+1;
    vii cr={ii{-INF,-1},ii{INF,0}};
    for(lli j=0;j<n;j++)
        cr.eb(ii{a[j].X,j});

sort(all(cr));
    const lli M = sz(cr);
    atcoder::segtree<S, op, e> seg(M);
    ordered_set<ii> os;

auto update=[&](const lli idx,const lli v)->void{
        const lli ci = lower_bound(all(cr),ii{a[idx].X,idx})-cr.begin();
        auto g = seg.get(ci);
        if(a[idx].Y){
            g[0]+=a[idx].X*v;
            g[1]+=v;
        } else {
            g[2]+=v;
        }
        seg.set(ci,g);
    };

for(lli i=0;i<n;i++){
        os.insert(ii{a[i].X,i});
        update(i,1);
    }

auto chk=[&](const lli K,const lli med)->bool{
        const lli ci = lower_bound(all(cr),ii{med,-2})-cr.begin();
        const auto pd = seg.prod(ci,M);
        const lli reqCnt = bigCnt - pd[1]-pd[2];
        dbg(med,reqCnt);
        if(reqCnt<=0)
            return true;
        target=reqCnt+1;
        const lli lr = seg.min_left<f>(ci);
        const auto pd2 = seg.prod(lr,ci);
        dbg(pd2[1],pd2[0],cr[lr]);
        if(pd2[1]<reqCnt)
            return false;
        return pd2[1]*med-pd2[0]<=K;
    };

auto getMedian = [&](const lli K)->lli{
        if(K==0)
            return os.find_by_order(medIdx)->X;
        lli l=0,r=INF;
        while(r-l>1){
            const lli mid=(l+r)/2;
            if(chk(K,mid))
                l=mid;
            else
                r=mid;
        }
        dbg(K,l,os);
        return l;
    };

for(lli i=0;i<n;i++){
        os.erase(ii{a[i].X,i});
        update(i,-1);
        if(a[i].Y==0)
            ans=max(ans,a[i].X+getMedian(K));
        else
            ans=max(ans,a[i].X+K+getMedian(0));
        os.insert(ii{a[i].X,i});
        update(i,1);
    }

cout<<ans<<endl;
}   aryanc403();
    return 0;
}

Changed text

Open file

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder

namespace atcoder {

#if __cplusplus >= 201703L

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

S all_prod() const { return d[1]; }

private:
    int _n, size, log;
    std::vector<S> d;

void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

using lli = long long int;
using mytype = long double;
using ii = pair<lli,lli>;
using vii = vector<ii>;
using vi = vector<lli>;

// namespace Re = std::ranges;
// namespace Ve = std::ranges::views;

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

using S = array<lli,3>;
S op(S a, S b) { return S{a[0]+b[0],a[1]+b[1],a[2]+b[2]}; }
S e() { return S{0,0,0}; }

int target;
bool f(S v) { return v[1]<target; }

sort(all(cr));
    const lli M = sz(cr);
    atcoder::segtree<S, op, e> seg(M);
    ordered_set<ii> os;

for(lli i=0;i<n;i++){
        os.insert(ii{a[i].X,i});
        update(i,1);
    }

auto getMedian = [&](const lli K)->lli{
        if(K==0)
            return os.find_by_order(medIdx)->X;
        lli l=0,r=4e9;
        while(r-l>1){
            const lli mid=(l+r)/2;
            if(chk(K,mid))
                l=mid;
            else
                r=mid;
        }
        dbg(K,l,os);
        return l;
    };

cout<<ans<<endl;
}   aryanc403();
    return 0;
}