Submission #302560

#	Time	Username	Problem	Language	Result	Execution time	Memory
302560		kevinsogo	Holiday (IOI14_holiday)	C++17	100 / 100	1777 ms	48756 KiB

holiday

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

template<class T>
void sort_uniq(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

struct Tree {
    int i, j;
    int v; ll s = 0;
    int c = 0;
    Tree *l, *r;
    Tree(const vector<int>& vs, int i, int j): i(i), j(j), v(vs[i]) {
        if (j - i == 1) {
            l = r = nullptr;
        } else {
            int k = i + j >> 1;
            l = new Tree(vs, i, k);
            r = new Tree(vs, k, j);
        }
    }

    void clear() {
        s = 0;
        c = 0;
        if (l) l->clear(), r->clear();
    }

    void inc(int I) {
        if (i <= I && I < j) {
            c++;
            if (l) {
                l->inc(I);
                r->inc(I);
                s = l->s + r->s;
            } else {
                s += v;
            }
        }
    }

    ll get(int k, ll t = 0) {
        tie(k, t) = _get(k, t);
        return t;
    }

    pair<int,ll> _get(int k, ll t) {
        if (k > 0 && c > 0) {
            if (k >= c) {
                t += s;
                k -= c;
            } else if (l) {
                tie(k, t) = r->_get(k, t);
                tie(k, t) = l->_get(k, t);
            } else {
                int u = min(k, c);
                t += (ll)u * v;
                k -= u;
            }
        }
        return {k, t};
    }
};

vector<ll> solve_all(vector<int> a, int x) {
    vector<int> vals = a;
    sort_uniq(vals);
    unordered_map<int,int> vali;
    for (int i = 0; i < vals.size(); i++) vali[vals[i]] = i;
    for (int i = 0; i < a.size(); i++) a[i] = vali[a[i]];

    vector<ll> wins((x + 1) * a.size(), -1);
    vector<tuple<int,int,int,int>> layer, nlayer;
    layer.emplace_back(0, wins.size() - 1, 0, a.size() - 1);
    Tree available(vals, 0, vals.size());
    int lay = 0;
    while (!layer.empty()) {
        available.clear();
        int p = 0;
        for (auto& lay : layer) {
            int di, dj, ei, ej;
            tie(di, dj, ei, ej) = lay;
            assert(ei <= ej);
            if (di > dj) continue;
            int d = di + dj >> 1, e = -1;
            for (int ee = ei; ee <= ej; ee++) {
                while (p <= ee) available.inc(a[p++]);
                ll w = available.get(d - x*ee);
                if (wins[d] < w) {
                    wins[d] = w;
                    e = ee;
                }
            }
            nlayer.emplace_back(di, d-1, ei, e);
            nlayer.emplace_back(d+1, dj, e, ej);
        }
        layer = nlayer;
        nlayer.clear();
    }

    return wins;
}

template<class T>
ll geet(const vector<T>& v, int i) {
    return i < v.size() ? v[i] : v.back();
}

ll solve_right(int start, int d, const vector<int>& a) {
    vector<int> l, r;
    for (int i = start; i >= 0; i--) l.push_back(a[i]);
    for (int i = start; i < a.size(); i++) r.push_back(a[i]);
    r[0] = 0;
    vector<ll> winl = solve_all(l, 2);
    vector<ll> winr = solve_all(r, 1);

    ll ans = 0;
    for (int x = 0; x <= d; x++) {
        ans = max(ans, geet(winl, x) + geet(winr, d - x));
    }

    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<int> a(attraction, attraction + n);
    ll ans = solve_right(start, d, a);
    reverse(a.begin(), a.end());
    return max(ans, solve_right(n - 1 - start, d, a));
}

Compilation message (stderr)

holiday.cpp: In constructor 'Tree::Tree(const std::vector<int>&, int, int)':
holiday.cpp:21:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |             int k = i + j >> 1;
      |                     ~~^~~
holiday.cpp: In function 'std::vector<long long int> solve_all(std::vector<int>, int)':
holiday.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < vals.size(); i++) vali[vals[i]] = i;
      |                     ~~^~~~~~~~~~~~~
holiday.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < a.size(); i++) a[i] = vali[a[i]];
      |                     ~~^~~~~~~~~~
holiday.cpp:89:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |             int d = di + dj >> 1, e = -1;
      |                     ~~~^~~~
holiday.cpp:80:9: warning: unused variable 'lay' [-Wunused-variable]
   80 |     int lay = 0;
      |         ^~~
holiday.cpp: In function 'll solve_right(int, int, const std::vector<int>&)':
holiday.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i = start; i < a.size(); i++) r.push_back(a[i]);
      |                         ~~^~~~~~~~~~
holiday.cpp: In instantiation of 'll geet(const std::vector<_Tp>&, int) [with T = long long int; ll = long long int]':
holiday.cpp:123:36:   required from here
holiday.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     return i < v.size() ? v[i] : v.back();

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