Confronta il testo

Trova la differenza tra due file di testo

Visualizzazione

Layout

Editor liveNascondi spazi bianchiComprimi invariateSenza a capo

Livello di dettaglio

Sintassi

Elaborazione

Diffchecker Desktop Il modo più sicuro per usare Diffchecker. Ottieni l'app Diffchecker Desktop: i tuoi diff non lasciano mai il tuo computer!Ottieni Desktop

Untitled diff

Creato 2 anni faIl diff non scade mai

1 rimozione

Linee
Totale
Rimosso

Caratteri
Totale
Rimosso

Per continuare a utilizzare questa funzione, aggiorna a Diffchecker Pro Visualizza prezzi

371 linee

1 aggiunta

Linee
Totale
Aggiunto

Caratteri
Totale
Aggiunto

Per continuare a utilizzare questa funzione, aggiorna a Diffchecker Pro Visualizza prezzi

371 linee

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

}

Diff salvati

Testo originale

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

Testo modificato

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