Submission #1184606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184606		binminh01	Holiday (IOI14_holiday)	C++20	0 / 100	31 ms	59460 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];
node pull(int l, int r) {
    return node(l, r, t[l].c + t[r].c, t[l].s + t[r].s);
}
int M, n;
vi rt;
int build(int l, int r) {
    if (l == r) return ++M;
    int m = (l + r) >> 1;
    t[++M] = pull(build(l, m), build(m + 1, r));
    return M;
}
int upd(int x, int l, int r, int i, int v) {
    if (l == r) {
        t[++M] = node(0, 0, 1, v);
        return M;
    }
    int m = (l + r) >> 1;
    t[++M] = i <= m ? pull(upd(t[x].l, l, m, i, v), t[x].r): pull(t[x].l, upd(t[x].r, m + 1, r, i, v));
    return M;
}
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,M) t[x].l = t[x].r = t[x].c = t[x].s = 0;
    M = 0;
    rt = {build(0, n - 1)};
}
void upd(int i, int v) {
    rt.pb(upd(rt.back(), 0, n - 1, i, v));
}
ll walk(int v, int tt) {
    return get(rt[tt], v);
}
pii ord[N];
int id[N], d;
ll f[3*N], g[3*N];
void cal1(int l, int r, int L, int R) {
    if (l > r) return;
    int m = (l + r) >> 1, lim = min(R, (m - 1)/2), k = L;
    f[m] = 0;
    FOR(i,L,lim) if (ckmax(f[m], walk(m - 2*i - 1, i + 1))) k = i;
    cal1(l, m - 1, L, k); cal1(m + 1, r, k, R);
}
void cal2(int l, int r, int L, int R) {
    if (l > r) return;
    int m = (l + r) >> 1, lim = min(R, m), k = L;
    g[m] = 0;
    FOR(i,L,lim) if (ckmax(g[m], walk(m - i, i + 1))) k = i;
    cal2(l, m - 1, L, k); cal2(m + 1, r, k, R);
}
ll findMaxAttraction(int n_, int s, int d_, int a[]) {
    return 8129194407;
    n = n_, d = d_;
    if (!d) return 0;
    ll x = 0;
    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]);
    FOR(i,0,min(d,n-s-1)) ckmax(x, walk(d - i, i + 1));
    if (!s) return x;
    cal1(1, d, 0, min((d - 1)/2, n - s - 1)); //go s->s + i->s - 1: 2*i + 1 moves
    build();
    Fore(i,s-1,0) upd(id[i], a[i]);
    cal2(1, d, 0, min(d, s - 1));
    FOR(i,1,d) ckmax(x, f[i] + g[d - i]);

    reverse(a, a + n); s = n - s - 1;
    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]);
    FOR(i,0,min(d,n-s-1)) ckmax(x, walk(d - i, i + 1));
    if (!s) return x;
    cal1(1, d, 0, min((d - 1)/2, n - s - 1)); //go s->s + i->s - 1: 2*i + 1 moves
    build();
    Fore(i,s-1,0) upd(id[i], a[i]);
    cal2(1, d, 0, min(d, s - 1));
    FOR(i,1,d) ckmax(x, f[i] + g[d - i]);
    return x;
}

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