Submission #297836

#	Time	Username	Problem	Language	Result	Execution time	Memory
297836		juckter	Holiday (IOI14_holiday)	C++14	0 / 100	102 ms	65540 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

struct node {
    int l, r;
    ll cnt, val;
    node *left, *right;

    node(int l, int r, int c = 0, ll v = 0) : l(l), r(r), cnt(c), val(v), left(nullptr), right(nullptr) {}
    ~node() {
        if(!this)
            return;
        cerr << l << " " << r << endl;
        if(left != nullptr) {
            cerr << "KILL LEFT " << left->l << endl;
            delete left;
        }
        if(right != nullptr)
            delete right;
    }

    void merge() {
        cnt = left->cnt + right->cnt;
        val = left->val + right->val;
    }

    void build() {
        if(l != r) {
            int m = (l + r) / 2;
            left = new node(l, m);
            right = new node(m + 1, r);
            left->build();
            right->build();
        }
    }

    node* upd(int p, ll v) {
        if(l == r)
            return new node(l, r, 1, v);
        node* result = new node(l, r);
        int m = (l + r) / 2;
        result->left = (p <= m ? left->upd(p, v) : left);
        result->right = (p > m ? right->upd(p, v) : right);
        result->merge();
        return result;
    }

    ll bsum(ll amt) {
        //cerr << amt << " " << l << " " << r << endl;
        if(amt == 0)
            return 0;
        if(amt >= cnt)
            return val;
        if(amt <= right->cnt)
            return right->bsum(amt);
        return right->val + left->bsum(amt - right->cnt);
    }

    void dbg() {
        //cerr << "[" << l << ", " << r << "] cnt = " << cnt << " val = " << val << endl;
        if(l < r) {
            left->dbg();
            right->dbg();
        }
    }
};

vector<node*> trees;

void solve(vector<ll> &dp, vector<ll> &opt, int L, int R, int oL, int oR) {
    //cerr << "Solving [" << L << ", " << R << "]   [" << oL << ", " << oR << "]" << endl;
    if(L > R)
        return;
    int m = (L + R) / 2;
    ll cur = -1;
    int cut = 0;
    for(int rest = oL; rest <= min(oR, m); rest++) {
        //cerr << "Querying tree " << rest << endl;
        ll res = trees[rest]->bsum(m - rest);
        if(res > cur) {
            cur = res;
            cut = rest;
        }
    }
    dp[m] = cur;
    opt[m] = cut;
    solve(dp, opt, L, m - 1, oL, cut);
    solve(dp, opt, m + 1, R, cut, oR);
}

void extreme(vector<ll> &at, vector<ll> &dp, vector<ll> &opt) {
    int n = at.size();
    dp.resize(2*n);
    opt.resize(2*n);
    
    vector<ii> pas(n);
    for(int i = 0; i < n; i++)
        pas[i] = {at[i], i};
    sort(pas.begin(), pas.end());
    //for(int i = 0; i < n; i++)
    //    cerr << pas[i].first << " " << pas[i].second << endl;
    vector<ii> comp(n);
    for(int i = 0; i < n; i++)
        comp[pas[i].second] = ii{i, pas[i].first};

    //for(int i = 0; i < n; i++)
    //    cerr << comp[i].first << " " << comp[i].second << endl;

    node* ini = new node(0, n - 1);
    ini->build();
    trees.push_back(ini->upd(comp[0].first, comp[0].second));
    for(int i = 1; i < n; i++)
        trees.push_back(trees.back()->upd(comp[i].first, comp[i].second));

    //for(int i = 0; i < n; i++) {
        //cerr << "TREE " << i << "\n===\n";
        //trees[i]->dbg();
        //cerr << "===" << endl;
    //}
    solve(dp, opt, 0, 2*n - 1, 0, n - 1);

    /*cerr << "ALL GOOD" << endl;
    for(int i = 0; i < trees.size(); i++) {
        if(trees[i]) {
            delete trees[i];
            cerr << "DELETED " << i << endl;
        }
    }
    if(ini)
        delete ini;*/

    //cerr << "SOLVED" << endl;
    //for(int i = 0; i < 2*n; i++) {
    //    cerr << i << " " << dp[i] << " " << opt[i] << endl;
    //}
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(start != 0)
        return 0;

    vector<ll> dp, opt, at;
    at.resize(n);
    for(int i = 0; i < n; i++)
        at[i] = attraction[i];

    extreme(at, dp, opt);
    //cerr << "GOOD" << endl;
    //cerr << dp.size() << " " << opt.size() << endl;
    //for(int i = 0; i < dp.size(); i++) {
    //    assert(i < opt.size());
    //    cerr << i << " " << dp[i] << " " << opt[i] << endl;
    //}
    return dp[min(d, 2*n - 1)];
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53