Submission #286866

#	Time	Username	Problem	Language	Result	Execution time	Memory
286866		tcm	Holiday (IOI14_holiday)	C++14	100 / 100	729 ms	12544 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define X first
#define Y second

using namespace std;
typedef pair<ll, int> li;
const int N = 100001, D = 2*N + N/2;
int n, s, d, sz, lg, arr[N], val[N];
ll R[D], RR[D], L[D], LL[D];
li fen[N];

void compress()
{
    set<int> s(arr + 1, arr + n + 1);
    vector<int> tmp(s.begin(), s.end());
    sz = tmp.size();
    lg = 32 - __builtin_clz(sz) - 1;
    int v;
    REP1(i, n) {
        v = sz - (lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin());
        val[v] = arr[i];
        arr[i] = v;
    }
}
void update(int pos)
{
    for(int i = pos; i <= sz; i += i&-i) {
        fen[i].X += val[pos];
        ++fen[i].Y;
    }
}
void rollback(int pos)
{
    for(int i = pos; i <= sz; i += i&-i) {
        fen[i].X -= val[pos];
        --fen[i].Y;
    }
}
li binsearch(int value)
{
    int p = 0, v = 0, jump;
    REPB0(i, lg + 1) {
        jump = p + (1 << i);
        if(jump <= sz && v + fen[jump].Y < value) {
            p = jump;
            v += fen[p].Y;
        }
    }
    if(p == sz) return {0, p};
    return {(value - v) * (ll)val[p + 1], p};
}
ll getSum(int pos)
{
    ll sum = 0;
    for(int i = pos; i; i &= i - 1)
        sum += fen[i].X;
    return sum;
}
void solveR(ll l, ll r, int from, int to)
{
    if(l > r) return;
    int pos = from, last = to + 1, mid = l + r >> 1;
    li p;
    ll res = -1, cur;
    FOR(i, from, to) {
        if(i - s >= mid) {
            last = i;
            break;
        }
        update(arr[i]);
        p = binsearch(mid - i + s);
        cur = p.X + getSum(p.Y);
        if(cur > res) {
            res = cur;
            pos = i;
        }
    }
    if(res != -1) R[mid] = res;
    FOR(i, pos, min(to, last - 1)) rollback(arr[i]);
    solveR(mid + 1, r, pos, to);
    FOR(i, from, pos - 1) rollback(arr[i]);
    solveR(l, mid - 1, from, pos);
}
void solveRR(int l, int r, int from, int to)
{
    if(l > r) return;
    int pos = from, last = to + 1, mid = l + r >> 1;
    li p;
    ll res = -1, cur;
    FOR(i, from, to) {
        if(2*(i - s) >= mid) {
            last = i;
            break;
        }
        update(arr[i]);
        p = binsearch(mid - 2*(i - s));
        cur = p.X + getSum(p.Y);
        if(cur > res) {
            res = cur;
            pos = i;
        }
    }
    if(res != -1) RR[mid] = res;
    FOR(i, pos, min(last - 1, to)) rollback(arr[i]);
    solveRR(mid + 1, r, pos, to);
    FOR(i, from, pos - 1) rollback(arr[i]);
    solveRR(l, mid - 1, from, pos);
}
void solveL(int l, int r, int from, int to)
{
    if(l > r) return;
    int pos = to, last = from - 1, mid = l + r >> 1;
    li p;
    ll res = -1, cur;
    FORB(i, to, from) {
        if(s - i >= mid) {
            last = i;
            break;
        }
        update(arr[i]);
        p = binsearch(mid - s + i);
        cur = p.X + getSum(p.Y);
        if(cur > res) {
            res = cur;
            pos = i;
        }
    }
    if(res != -1) L[mid] = res;
    FOR(i, max(last + 1, from), pos) rollback(arr[i]);
    solveL(mid + 1, r, from, pos);
    FOR(i, pos + 1, to) rollback(arr[i]);
    solveL(l, mid - 1, pos, to);
}
void solveLL(int l, int r, int from, int to)
{
    if(l > r) return;
    int pos = to, last = from - 1, mid = l + r >> 1;
    li p;
    ll res = -1, cur;
    FORB(i, to, from) {
        if(2*(s - i) >= mid) {
            last = i;
            break;
        }
        update(arr[i]);
        p = binsearch(mid - 2*(s - i));
        cur = p.X + getSum(p.Y);
        if(cur > res) {
            res = cur;
            pos = i;
        }
    }
    if(res != -1) LL[mid] = res;
    FOR(i, max(last + 1, from), pos) rollback(arr[i]);
    solveLL(mid + 1, r, from, pos);
    FOR(i, pos + 1, to) rollback(arr[i]);
    solveLL(l, mid - 1, pos, to);
}
long long int findMaxAttraction(int nn, int start, int dd, int attraction[]) {
    n = nn;
    s = start + 1;
    d = dd;
    REP1(i, n) arr[i] = attraction[i - 1];
    compress();
    solveR(1, d, s, n);
    solveRR(1, d, s, n);
    if(s > 1) {
        solveL(2, d, 1, s - 1);
        solveLL(2, d, 1, s - 1);
    }
    long long int ans = 0;
    REP0(t, d + 1) {
        ans = max(ans, L[t] + RR[d - t]);
        ans = max(ans, LL[t] + R[d - t]);
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void solveR(long long int, long long int, int, int)':
holiday.cpp:70:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int pos = from, last = to + 1, mid = l + r >> 1;
      |                                          ~~^~~
holiday.cpp: In function 'void solveRR(int, int, int, int)':
holiday.cpp:95:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |     int pos = from, last = to + 1, mid = l + r >> 1;
      |                                          ~~^~~
holiday.cpp: In function 'void solveL(int, int, int, int)':
holiday.cpp:120:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |     int pos = to, last = from - 1, mid = l + r >> 1;
      |                                          ~~^~~
holiday.cpp: In function 'void solveLL(int, int, int, int)':
holiday.cpp:145:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |     int pos = to, last = from - 1, mid = l + r >> 1;
      |                                          ~~^~~

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