Submission #1155985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155985		binminh01	Holiday (IOI14_holiday)	C++20	23 / 100	184 ms	63316 KiB

holiday

#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt,tune=native")

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ret(s) return void(cout << s);

constexpr int mod = 1e9 + 7, mod2 = 998244353;
constexpr double eps = 1e-9;
const double PI = acos(-1);
constexpr ull npos = string::npos;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using cd = complex<double>;
mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 mt64(chrono::system_clock::now().time_since_epoch().count());
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<cd> vcd;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;
template<class A, class B> bool ckmin(A &a, const B &b) {return a > b ? a = b, 1: 0;}
template<class A, class B> bool ckmax(A &a, const B &b) {return a < b ? a = b, 1: 0;}

#include"holiday.h"
constexpr int N = 1e5 + 5;
struct node {
    int l, r, c; ll s;
    node(int l = 0, int r = 0, int c = 0, ll s = 0): l(l), r(r), c(c), s(s) {}
} t[25*N];
void push(int x) {
    t[x].c = t[t[x].l].c + t[t[x].r].c;
    t[x].s = t[t[x].l].s + t[t[x].r].s;
}
int tot, cv, n, ver[N];
void build(int x, int l, int r) {
    if (l == r) {
        ckmax(tot, x);
        return;
    }
    int m = (l + r) >> 1;
    t[x].l = x << 1; t[x].r = x << 1|1;
    build(t[x].l, l, m); build(t[x].r, m + 1, r);
}
int upd(int x, int l, int r, int i, int v) {
    int cur = ++tot;
    if (l == r) {
        t[cur].c = 1; t[cur].s = v;
        return cur;
    }
    int m = (l + r) >> 1;
    if (i <= m) {
        t[cur].l = tot + 1; t[cur].r = t[x].r;
        upd(t[x].l, l, m, i, v);
    } else {
        t[cur].l = t[x].l; t[cur].r = tot + 1;
        upd(t[x].r, m + 1, r, i, v);
    }
    push(cur);
    return cur;
}
ll get(int x, int v) {
    if (t[x].c <= v) return t[x].s;
    if (t[t[x].l].c >= v) return get(t[x].l, v);
    return t[t[x].l].s + get(t[x].r, v - t[t[x].l].c);
}
void build() {
    FOR(x,0,tot) t[x].l = t[x].r = t[x].c = t[x].s = 0;
    tot = cv = 0; ver[0] = 1;
    build(1, 0, n - 1);
}
void upd(int i, int v) {
    int x = upd(ver[cv], 0, n - 1, i, v);
    ver[++cv] = x;
}
ll walk(int v, int tt) {
    return get(ver[tt], v);
}
pii ord[N];
int id[N];
ll f[2*N], g[2*N];
int pf[2*N], pg[2*N];
void cal1(int l, int r, int L, int R) {
    if (l > r) return;
    int m = (l + r) >> 1, lim = min(R, m);
    pf[m] = L;
    FOR(i,L,lim) if (ckmax(f[m], walk(m - i, i + 1))) pf[m] = i;
    cal1(l, m - 1, L, pf[m]); cal1(m + 1, r, pf[m], R);
}
void cal2(int l, int r, int L, int R) {
    if (l > r) return;
    int m = (l + r) >> 1, lim = min(R, m);
    pg[m] = L;
    FOR(i,L,lim) if (ckmax(g[m], walk(m - i, i + 1))) pg[m] = i;
    cal2(l, m - 1, L, pg[m]); cal2(m + 1, r, pg[m], R);
}
ll findMaxAttraction(int n_, int s, int d, int a[]) {
    n = n_;
    build();
    For(i,0,n) ord[i] = {a[i], i};
    sort(ord, ord + n, greater<>());
    For(i,0,n) id[ord[i].second] = i;
    For(i,s,n) upd(id[i], a[i]);
    cal1(1, d, 0, n - s - 1);
    if (!s) return f[d];
    build();
    Fore(i,s-1,0) upd(id[i], a[i]);
    cal2(1, d, 0, s - 1);
    ll x = 0;
    FOR(i,0,d){
        ll y = f[i];
        int j = d - i - pf[i] - 1;
        if (j >= 0) y+=g[j];
        ckmax(x, y);
        if (i) {
            y = g[i - 1];
            j = d - i - pg[i - 1] - 1;
            if (j >= 0) y+=f[j];
            ckmax(x, y);
            ckmax(x, g[i - 1] + a[s]);
        }
    }
    return x;
}

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