Comparar texto

Encuentra la diferencia entre dos archivos de texto

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

Herramientas

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

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker Desktop Learn more

Untitled diff

Created 3 months agoDiff never expires

1 removal

371 lines

1 addition

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;

}

Diffs guardadas

Texto original

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;
}

Texto modificado

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;
}