제출 #241534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241534		abacaba	휴가 (IOI14_holiday)	C++14	24 / 100	110 ms	65540 KiB

holiday

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}

inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}

template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}

template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int inf = 1e9;
const int mod = 998244353;
const int N = 3e5 + 15;
int a[N];
ll sum1, sum2;

vector <int> comp;

pair <ll, int> f[N], g[N];

struct node {
    node *l, *r;
    ll sum;
    int cnt;
    inline void copy(node *t) {
        if(t)
            l = t->l, r = t->r, sum = t->sum, cnt = t->cnt;
        else
            l = r = NULL, sum = 0, cnt = 0;
    }
    node(node *_l = NULL, node *_r = NULL) {
        l = _l, r = _r;
        sum = cnt = 0;
        if(l)
            sum += l->sum, cnt += l->cnt;
        if(r)
            sum += r->sum, cnt += r->cnt;
    }
};

typedef node* pnode;

vector <pnode> root = {NULL};

inline int get_cnt(pnode t) {
    return t ? t->cnt : 0;
}

inline ll get_sum(pnode t) {
    return t ? t->sum : 0LL;
}

inline pnode get_r(pnode &t) {
    return t ? t->r : t;
}

inline pnode get_l(pnode &t) {
    return t ? t->l : t;
}

pnode update(pnode t, int tl, int tr, int pos) {
    if(tl == tr) {
        pnode nw = new node(t);
        ++nw->cnt, nw->sum += comp[tl - 1];
        return nw;
    }
    int mid = tl + tr >> 1;
    if(pos <= mid)
        return new node(update(get_l(t), tl, mid, pos), get_r(t));
    return new node(get_l(t), update(get_r(t), mid + 1, tr, pos));
}

ll get_sum_of_k(pnode t1, pnode t2, int tl, int tr, int k) {
    if(k <= 0)
        return 0;

    int cnt = get_cnt(t2) - get_cnt(t1);

    if(cnt <= k)
        return get_sum(t2) - get_sum(t1);

    if(tl == tr)
        return 1LL * k * comp[tl - 1];

    int mid = tl + tr >> 1;

    int cntr = get_cnt(get_r(t2)) - get_cnt(get_r(t1));

    return get_sum_of_k(get_l(t1), get_l(t2), tl, mid, k - cntr) + get_sum_of_k(get_r(t1), get_r(t2), mid + 1, tr, k);
}

inline int gt(int x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
}

inline void calc_f(int start, int l, int r, int opt_l, int opt_r) {
    if(l > r)
        return;
    int mid = l + r >> 1;
    f[mid] = {-1, -inf};

    for(int i = opt_l; i <= opt_r; ++i)
        Max(f[mid], mp(get_sum_of_k(root[start - 1], root[i], 1, comp.size(), mid - 2 * (i - start)), -i));

    f[mid].se *= -1;

    assert(f[mid].f != -1);

    calc_f(start, l, mid - 1, opt_l, f[mid].se);
    calc_f(start, mid + 1, r, f[mid].se, opt_r);
}

inline void calc_g(int start, int l, int r, int opt_l, int opt_r) {
    if(l > r)
        return;
    int mid = l + r >> 1;
    g[mid] = {-1, -inf};

    for(int i = opt_l; i <= opt_r; ++i)
        Max(g[mid], mp(get_sum_of_k(root[i - 1], root[start - 1], 1, comp.size(), mid - (start - 1 - i)), i));

    assert(g[mid].f != -1);

    calc_g(start, l, mid - 1, g[mid].se, opt_r);
    calc_g(start, mid + 1, r, opt_l, g[mid].se);
}

inline void calc(ll &ans, int start, int n, int d) {
    if(start == 1 || start == n)
        return;

    calc_f(start, 0, d, start, n);
    calc_g(start, 0, d, 1, start - 1);

    for(int x = 0; x <= d; ++x) {
        int i = f[x].se;
        int lef = d - x - 1;
        if(lef >= 0)
            Max(ans, g[lef].f + f[x].f);
    }
}

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

    for(int i = 1; i <= n; ++i)
        comp.pb(a[i]);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    for(int i = 1; i <= n; ++i)
        root.pb(update(root.back(), 1, comp.size(), gt(a[i])));

    ++start;

    ll ans = 0;

    for(int i = start; i <= n; ++i)
        Max(ans, get_sum_of_k(root[start - 1], root[i], 1, comp.size(), d - (i - start)));
    for(int i = start; i >= 1; --i)
        Max(ans, get_sum_of_k(root[i - 1], root[start], 1, comp.size(), d - (start - i)));

    calc(ans, start, n, d);

    reverse(a + 1, a + 1 + n);
    start = n - start + 1;
    root = {NULL};
    for(int i = 1; i <= n; ++i)
        root.pb(update(root.back(), 1, comp.size(), gt(a[i])));

    calc(ans, start, n, d);
    return ans;
}

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

holiday.cpp: In function 'node* update(pnode, int, int, int)':
holiday.cpp:117:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~
holiday.cpp: In function 'long long int get_sum_of_k(pnode, pnode, int, int, int)':
holiday.cpp:135:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~
holiday.cpp: In function 'void calc_f(int, int, int, int, int)':
holiday.cpp:149:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
holiday.cpp: In function 'void calc_g(int, int, int, int, int)':
holiday.cpp:166:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
holiday.cpp: In function 'void calc(long long int&, int, int, int)':
holiday.cpp:186:13: warning: unused variable 'i' [-Wunused-variable]
         int i = f[x].se;
             ^

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