Submission #1217362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217362		12345678	Tricks of the Trade (CEOI23_trade)	C++20	50 / 100	1057 ms	287700 KiB

trade

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=250005, inf=1e18;

ll n, k, c[nx], s[nx], qs[nx], dp[nx], opt[nx], ans=-inf, lst=1;
vector<pair<ll, ll>> srt;

struct persist
{
    struct node
    {
        ll f, sm;
        node *l, *r;
        node(): f(0), sm(0), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &k)
    {
        k=new node();
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md ,k->l);
        build(md+1, r, k->r);
    }
    void update(int l, int r, pnode &k, pnode p, int idx, ll vl)
    {
        k=new node(*p);
        if (l==r) return k->f=1, k->sm=vl, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, p->l, idx, vl);
        else update(md+1, r, k->r, p->r, idx, vl);
        k->f=k->l->f+k->r->f;
        k->sm=k->l->sm+k->r->sm;
    }
    ll query(int l, int r, pnode k, pnode p, int key)
    {
        if (l==r) return k->sm-p->sm;
        int md=(l+r)/2;
        if (k->r->f-p->r->f>=key) return query(md+1, r, k->r, p->r, key);
        else return k->r->sm-p->r->sm+query(l, md, k->l, p->l, key-k->r->f+p->r->f);
    }
    ll queryf(int l, int r, pnode k, pnode p, int key)
    {
        if (l==r) return k->sm;
        int md=(l+r)/2;
        if (k->r->f-p->r->f>=key) return queryf(md+1, r, k->r, p->r, key);
        else return queryf(l, md, k->l, p->l, key-k->r->f+p->r->f);
    }
} p;

void solve(int l, int r, int optl, int optr)
{
    if (r<l) return;
    int md=(l+r)/2;
    pair<ll, ll> mx={-inf, 0};
    for (int i=optl; i<=min((ll)optr, md-k+1); i++) mx=max(mx, {-qs[md]+qs[i-1]+p.query(1, n, p.rt[md], p.rt[i-1], k), i});
    dp[md]=mx.first;
    opt[md]=mx.second;
    solve(l, md-1, optl, opt[md]);
    solve(md+1, r, opt[md], optr);
}

vector<ll> add[nx], rem[nx];
multiset<ll> ms;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>c[i], qs[i]=qs[i-1]+c[i], dp[i]=-inf;
    for (int i=1; i<=n; i++) cin>>s[i], srt.push_back({s[i], i});
    sort(srt.begin(), srt.end());
    p.build(1, n, p.rt[0]);
    for (int i=1; i<=n; i++)
    {
        auto tmp=lower_bound(srt.begin(), srt.end(), make_pair(s[i], (ll)i))-srt.begin()+1;
        p.update(1, n, p.rt[i], p.rt[i-1], tmp, s[i]);
    }
    solve(k, n, 1, n);
    for (int i=1; i<=n; i++) ans=max(ans, dp[i]);
    for (int i=1; i<=n; i++)
    {
        if (dp[i]==ans)
        {
            for (int j=lst; j<=opt[i]; j++)
            {
                if (-qs[i]+qs[j-1]+p.query(1, n, p.rt[i], p.rt[j-1], k)==ans)
                {
                    auto tmp=p.queryf(1, n, p.rt[i], p.rt[j-1], k);
                    //cout<<"range "<<j<<' '<<i<<' '<<tmp<<'\n';
                    add[j].push_back(tmp);
                    rem[i].push_back(tmp);
                }
            }
            lst=opt[i];
        }
    }
    cout<<ans<<'\n';
    for (int i=1; i<=n; i++)
    {
        for (auto x:add[i]) ms.insert(x);
        if (!ms.empty()&&s[i]>=*ms.begin()) cout<<1;
        else cout<<0;
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 5 / 10
• Subtask 3: 5 / 10
• Subtask 4: 10 / 25
• Subtask 5: 25 / 45