Submission #297850

#	Time	Username	Problem	Language	Result	Execution time	Memory
297850		juckter	Holiday (IOI14_holiday)	C++14	100 / 100	2142 ms	18168 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) {
        if(l != r) {
            int m = (l + r) / 2;
            left = new node(l, m);
            right = new node(m + 1, r);
        }
    }
    ~node() {
        delete left;
        delete right;
    }

    void upd(int p, ll v) {
        if(p < l || r < p)
            return;
        if(l == r) {
            if(v == -1) {
                val = 0;
                cnt = 0;
            }
            else {
                val = v;
                cnt = 1;
            }
            return;
        }
        left->upd(p, v);
        right->upd(p, v);
        cnt = left->cnt + right->cnt;
        val = left->val + right->val;
    }

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

node *tree;
int curS;

void solve(vector<ii> &at, 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 << curS << " " << rest << endl;
        while(curS < rest) {
            curS++;
            //cerr << "Adding " << curS << endl;
            tree->upd(at[curS].first, at[curS].second);
        }
        while(curS > rest) {
            //cerr << "Removing " << curS << endl;
            tree->upd(at[curS].first, -1);
            curS--;
        }
        //cerr << "Tree at " << rest << endl; 
        //tree->dbg();
        //cerr << "Querying tree " << rest << endl;
        ll res = tree->bsum(m - rest);
        if(res > cur) {
            cur = res;
            cut = rest;
        }
    }
    dp[m] = cur;
    opt[m] = cut;
    solve(at, dp, opt, L, m - 1, oL, cut);
    solve(at, 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;

    tree = new node(0, n - 1);
    curS = -1;

    solve(comp, dp, opt, 0, 2*n - 1, 0, n - 1);

    delete tree;

    //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) {
        vector<ll> dp, opt, at;
        at.resize(n);
        for(int i = 0; i < n; i++)
            at[i] = attraction[i];

        extreme(at, dp, opt);
        return dp[min(d, 2*n - 1)];
    }

    if(start == n - 1) {
        vector<ll> dp, opt, at;
        at.resize(n);
        for(int i = n - 1; i >= 0; i--)
            at[i] = attraction[n - 1 - i];

        extreme(at, dp, opt);
        return dp[min(d, 2*n - 1)];
    }

    // Right then left, then left then right
    ll ans = 0;
    for(int it = 0; it < 2; it++) {
        vector<ll> ri, dpr, optr, le, dpl, optl;
        for(int i = start; i < n; i++)
            ri.push_back(attraction[i]);
        for(int i = start - 1; i >= 0; i--)
            le.push_back(attraction[i]);
        extreme(ri, dpr, optr);
        extreme(le, dpl, optl);
        /*cerr << "Right" << endl;
        for(int i = 0; i < dpr.size(); i++)
            cerr << i << " " << dpr[i] << " " << optr[i] << endl;
        
        cerr << "Left" << endl;
        for(int i = 0; i < dpl.size(); i++)
            cerr << i << " " << dpl[i] << " " << optl[i] << endl;*/

        for(int sri = 0; sri <= min((int)dpr.size() - 1, d); sri++) {
            int trav = optr[sri];
            ans = max(ans, dpr[sri]);
            if(sri + trav + 1 > d)
                continue;
            ans = max(ans, dpr[sri] + dpl[min(d - sri - trav - 1, (int)dpl.size() - 1)]);
        }
        reverse(attraction, attraction + n);
        start = n - 1 - start;
    }
    return ans;
}

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