제출 #900660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900660		vjudge1	Holiday (IOI14_holiday)	C++17	100 / 100	1048 ms	10452 KiB

holiday

// https://oj.uz/problem/view/IOI14_holiday

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

namespace std {

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
        auto fun = y_combinator([&](auto self, int x) -> void {
                self(x + 1);
        });
*/

}  // namespace std

const int N = 1e5;
struct segtree {
       private:
        int n;
        vector<int64_t> val;
        vector<int> cnt;

        void assign(int i, int l, int r, int p, int64_t x, int y) {
                if (l == r) {
                        val[i] = x;
                        cnt[i] = y;
                        return;
                }
                int m = l + r >> 1;
                if (p <= m) {
                        assign(i << 1, l, m, p, x, y);
                } else {
                        assign(i << 1 | 1, m + 1, r, p, x, y);
                }
                val[i] = val[i << 1] + val[i << 1 | 1];
                cnt[i] = cnt[i << 1] + cnt[i << 1 | 1];
        }

        int64_t get(int i, int l, int r, int x) {
                if (l == r) return x >= cnt[i] ? val[i] : 0;
                int m = l + r >> 1;
                if (cnt[i << 1] >= x) return get(i << 1, l, m, x);
                return val[i << 1] + get(i << 1 | 1, m + 1, r, x - cnt[i << 1]);
        }

       public:
        segtree(int n = 0) : n(n) {
                val.assign(n * 4 + 7, 0);
                cnt.assign(n * 4 + 7, 0);
        }

        void assign(int p, int64_t x, int y) {
                assign(1, 0, n - 1, p, x, y);
        }

        int64_t get(int x) {
                return get(1, 0, n - 1, x);
        }
};

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) a[i] = attraction[i];

        auto solve = [&](int n, int prod, const vector<int> &a) {
                int d = n * (2 + prod);
                vector<int> ord(n);
                iota(ord.begin(), ord.end(), 0);
                sort(ord.begin(), ord.end(), [&](int i, int j) {
                        return a[i] > a[j];
                });
                vector<int> rev(n);
                for (int i = 0; i < n; i++) rev[ord[i]] = i;

                segtree tree(n);

                vector<int64_t> f(d);

                auto dnc = y_combinator([&](auto dnc, int l, int r, int low, int high) -> void {
                        if (l > r) return;
                        int m = l + r >> 1;
                        f[m] = -1;
                        int best = -1;
                        for (int i = low; i <= high; i++) {
                                tree.assign(rev[i], a[i], +1);
                                int64_t ans = tree.get(m - (i << prod));
                                if (f[m] < ans) f[m] = ans, best = i;
                        }
                        for (int i = low; i <= high; i++) tree.assign(rev[i], 0, 0);
                        dnc(l, m - 1, low, best);
                        for (int i = low; i < best; i++) tree.assign(rev[i], a[i], +1);
                        dnc(m + 1, r, best, high);
                });

                dnc(0, n * (2 + prod) - 1, 0, n - 1);

                return f;
        };
        int64_t res = 0;
        {
                vector<int> ra;
                for (int i = start; i < n; i++) ra.emplace_back(a[i]);
                auto r = solve(n - start, 1, ra);
                vector<int> la;
                for (int i = start - 1; i >= 0; i--) la.emplace_back(a[i]);
                auto l = solve(start, 0, la);

                for (int i = 0; i < r.size() && i <= d; i++) {
                        int64_t sum = r[i];
                        int rem = d - i - 1;
                        rem = min<int>(rem, l.size() - 1);
                        if (rem >= 0) sum += l[rem];
                        res = max(res, sum);
                }
        }
        {
                vector<int> ra;
                for (int i = start; i >= 0; i--) ra.emplace_back(a[i]);
                auto r = solve(start + 1, 1, ra);
                vector<int> la;
                for (int i = start + 1; i < n; i++) la.emplace_back(a[i]);
                auto l = solve(n - start - 1, 0, la);

                for (int i = 0; i < r.size() && i <= d; i++) {
                        int64_t sum = r[i];
                        int rem = d - i - 1;
                        rem = min<int>(rem, l.size() - 1);
                        if (rem >= 0) sum += l[rem];
                        res = max(res, sum);
                }
        }
        return res;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In member function 'void segtree::assign(int, int, int, int, int64_t, int)':
holiday.cpp:49:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |                 int m = l + r >> 1;
      |                         ~~^~~
holiday.cpp: In member function 'int64_t segtree::get(int, int, int, int)':
holiday.cpp:61:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |                 int m = l + r >> 1;
      |                         ~~^~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:128:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for (int i = 0; i < r.size() && i <= d; i++) {
      |                                 ~~^~~~~~~~~~
holiday.cpp:144:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |                 for (int i = 0; i < r.size() && i <= d; i++) {
      |                                 ~~^~~~~~~~~~
holiday.cpp: In instantiation of 'findMaxAttraction(int, int, int, int*)::<lambda(int, int, const std::vector<int>&)>::<lambda(auto:23, int, int, int, int)> [with auto:23 = std::reference_wrapper<std::y_combinator_result<findMaxAttraction(int, int, int, int*)::<lambda(int, int, const std::vector<int>&)>::<lambda(auto:23, int, int, int, int)> > >]':
holiday.cpp:19:28:   required from 'decltype(auto) std::y_combinator_result<Fun>::operator()(Args&& ...) [with Args = {int, int, int, int}; Fun = findMaxAttraction(int, int, int, int*)::<lambda(int, int, const std::vector<int>&)>::<lambda(auto:23, int, int, int, int)>]'
holiday.cpp:115:52:   required from here
holiday.cpp:101:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |                         int m = l + r >> 1;
      |                                 ~~^~~

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