Submission #1037032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037032		model_code	Tricks of the Trade (CEOI23_trade)	C++17	100 / 100	968 ms	142196 KiB

trade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll inf = 1e18;

struct Answer{
    ll maximum;
    ll rangeCnt;
    string optimalIndices;
};

int n, k;
vector<ll> a, b, bpr, result;
vector<int> opt, opt2;

constexpr int NODES = 1e7;
int nodeCnt, L[NODES], R[NODES], scnt[NODES];
ll ssum[NODES];

int supd(int p, ll v, int a, int b, int i){
    int node = nodeCnt++;
    L[node] = L[i];
    R[node] = R[i];
    if(a == b){
        ssum[node] = v;
        scnt[node] = 1;
        return node;
    }
    int m = (a+b)/2;
    if(p <= m) L[node] = supd(p, v, a, m, L[i]);
    else R[node] = supd(p, v, m+1, b, R[i]);
    scnt[node] = scnt[L[node]] + scnt[R[node]];
    ssum[node] = ssum[L[node]] + ssum[R[node]];
    return node;
}

// (sum, k-biggest)
pair<ll, ll> sqry(int goal, int add, int sub, int siz){
    if(siz == 1){
        assert(scnt[sub] == 0);
        return {ssum[add], ssum[add]};
    }
    int cr = scnt[R[add]] - scnt[R[sub]];
    if(cr < goal){
        auto [lsum, lkbig] = sqry(goal-cr, L[add], L[sub], siz/2);
        return {lsum + ssum[R[add]] - ssum[R[sub]], lkbig};
    }
    else{
        return sqry(goal, R[add], R[sub], siz/2);
    }
}

vector<int> roots;
int cap;

pair<ll, ll> qry(int l, int r){
    auto [sum, kbig] = sqry(k, roots[r+1], roots[l], cap);
    sum -= bpr[r+1] - bpr[l];
    return {sum, kbig};
}

void init(){
    roots.resize(n+1);
    for(cap=1; cap<n; cap*=2);
    roots[0] = 1;
    for(int i = cap-1; i >= 1; i--) L[i] = 2*i, R[i] = 2*i+1;
    nodeCnt = 2*cap;

    vector<pair<ll, int>> aind;
    for(int i = 0; i < n; i++) aind.emplace_back(a[i], i);
    sort(aind.begin(), aind.end());
    vector<int> ind(n);
    for(int i = 0; i < n; i++) ind[aind[i].second] = i;
    for(int i = 0; i < n; i++) roots[i+1] = supd(ind[i], a[i], 0, cap-1, roots[i]);

    bpr.resize(n+1);
    for(int i = 0; i < n; i++) bpr[i+1] = bpr[i] + b[i];
}

ll ans = -inf;

// minimum optimal index
void dc(int l, int r, int optL, int optR){
    if(l > r) return;
    int m = (l+r)/2;
    ll res = -inf; int ind = optR;
    for(int i = max(m+k-1, optL); i <= optR; i++){
        ll val = qry(m, i).first;
        if(val > res){
            res = val;
            ind = i;
        }
    }
    ans = max(ans, res);
    opt[m] = ind;
    result[m] = res;
    dc(l, m-1, optL, ind);
    dc(m+1, r, ind, optR);
}

Answer solve(){
    init();
    ans = -inf;
    opt.assign(n, -1);
    opt2.assign(n, -1);
    result.assign(n, -inf);

    dc(0, n-1, 0, n-1);
    Answer answer;
    answer.maximum = ans;
    // ans is calculated now.

    // optimal indices
    {
        vector<vector<ll>> add(n), rem(n+1);
        int nxt = 0;
        for(int i = 0; i < n; i++){
            if(result[i] != ans) continue;
            nxt = max(nxt, i+1);
            while(nxt < n && result[nxt] != ans) nxt++;
            int r = n-1;
            if(nxt != n) r = opt[nxt];
            for(int j = opt[i]; j <= r; j++){
                auto [val, kth] = qry(i, j);
                if(val == ans){
                    add[i].push_back(kth);
                    rem[j+1].push_back(kth);
                }
            }
        }
        string optimalIndices(n, '0');
        multiset<ll> active;
        for(int i = 0; i < n; i++){
            for(ll x : add[i]) active.insert(x);
            for(ll x : rem[i]) active.erase(active.find(x));
            if(active.empty()) continue;
            if(a[i] >= *active.begin()) optimalIndices[i] = '1';
        }
        answer.optimalIndices = optimalIndices;
    }

    return answer;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    a.resize(n), b.resize(n);
    for(int i = 0; i < n; i++) cin >> b[i];
    for(int i = 0; i < n; i++) cin >> a[i];
    Answer ans = solve();
    cout << ans.maximum << "\n";
    cout << ans.optimalIndices << "\n";
}

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