Submission #615979

#	Time	Username	Problem	Language	Result	Execution time	Memory
615979		Do_you_copy	Holiday (IOI14_holiday)	C++17	100 / 100	312 ms	48768 KiB

holiday

/*
 
F@CK YOU PERSISTENT DATA STRUCTURE
F@CK YOU SEGMENT TREE
F@CK MLE
NO POINTER PERSISTENT SEGMENT TREE CHALLENGE?
 
*/
 
 
#include <bits/stdc++.h>
#include "holiday.h"
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
 
ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}
 
ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}
 
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 2;
const int maxD = 3e5;
 
int n;
int node_cnt;
 
vector <ll> node;
struct __attribute__((packed)) TNode{
    int lp, rp;
    int val;
    ll sum;
    TNode(){};
    TNode(int _val, ll _sum) : lp(0), rp(0), val(_val), sum(_sum){}
    TNode(const TNode &left, const TNode &right){
        val = left.val + right.val;
        sum = left.sum + right.sum;
    }
};
 
TNode st[maxN * 25];
ll p[maxN];
pll ls[maxD];
pll rs[maxD];
int Start;
void build(int id, int i, int l = 1, int r = node.size()){
    if (l == r){
        if (l == i) st[id] = {1, node[i - 1]};
        else st[id] = {0, 0};
        return;
    }
    int mid = (l + r) / 2;
    int lp = ++node_cnt;
    build(lp, i, l, mid);
    int rp = ++node_cnt;
    build(rp, i, mid + 1, r);
    st[id] = {st[lp], st[rp]};
    st[id].lp = lp;
    st[id].rp = rp;
}
 
void update(int id, int last, int i, int l = 1, int r = node.size()){
    if (l == r){
        st[id] = {st[last].val + 1, st[last].sum + node[l - 1]};
        return;
    }
    int mid = (l + r) / 2;
    if (i <= mid){
        int lp = ++node_cnt;
        update(lp, st[last].lp, i, l, mid);
        st[id] = {st[lp], st[st[last].rp]};
        st[id].lp = lp;
        st[id].rp = st[last].rp;
    }
    else{
        int rp = ++node_cnt;
        update(rp, st[last].rp, i, mid + 1, r);
        st[id] = {st[st[last].lp], st[rp]};
        st[id].rp = rp;
        st[id].lp = st[last].lp;
    }
}
 
ll get(int id, int k, int l = 1, int r = node.size()){
    if (l == r){
        return k * node[l - 1];
    }
    int mid = (l + r) / 2;
    if (st[st[id].rp].val >= k) return get(st[id].rp, k, mid + 1, r);
    else return st[st[id].rp].sum + get(st[id].lp, k - st[st[id].rp].val, l, mid);
}
 
inline int pos(int i){
    return upper_bound(node.begin(), node.end(), i) - node.begin();
}
 
void DnCl(int s, int t, int l, int r){
    if (l > r || s < t){
        return;
    }
    int mid = (l + r) / 2;
    for (int i = s; i >= t; --i){
        ll tem = get(i, min(mid - (Start - i - 1), st[i].val));
        if (tem > ls[mid].fi){
            ls[mid].fi = tem;
            ls[mid].se = i;
        }
    }
    if (l == r) return;
    DnCl(s, ls[mid].se, l, mid - 1);
    DnCl(ls[mid].se, t, mid + 1, r);
}
 
void DnCr(int s, int t, int l, int r){
    if (l > r || s > t){
        return;
    }
    int mid = (l + r) / 2;
    rs[mid].se = s;
    for (int i = s; i <= t; ++i){
        ll tem = get(i, min(mid - (i - Start), st[i].val));
        if (tem > rs[mid].fi){
            rs[mid].fi = tem;
            rs[mid].se = i;
        }
    }
    if (l == r) return;
    DnCr(s, rs[mid].se, l, mid - 1);
    DnCr(rs[mid].se, t, mid + 1, r);
}
 
ll findMaxAttraction(int N, int start, int d, int attraction[]){
    n = N;
    ll sum = 0;
    for (int i = 0; i < n; ++i){
        p[i + 1] = attraction[i];
        node.pb(p[i + 1]);
        sum += p[i + 1];
    }
    if (d == 0) return 0;
    node.pb(0);
    sort(node.begin(), node.end());
    node.resize(unique(node.begin(), node.end()) - node.begin());
    ++start;
    node_cnt = n;
    build(start, pos(p[start]));
    build(start - 1, pos(p[start - 1]));
 
    for (int i = start + 1; i <= n; ++i){
        update(i, i - 1, pos(p[i]));
    }
    for (int i = start - 2; i >= 1; --i){
        st[i] = st[i + 1];
        update(i, i + 1, pos(p[i]));
    }
    Start = start;
    DnCr(start, n, 1, d);
    DnCl(start - 1, 1, 1, d);
    ll ans = ls[d - 1].fi;
    for (int i = 1; i <= d; ++i){
        int k = d - rs[i].se + start - 1 - i;
        if (k < 0) ans = max(ans, rs[i].fi);
        else ans = max(ans, ls[k].fi + rs[i].fi);
    }
    ans = max(ans, rs[d].fi);
    for (int i = 1; i < d; ++i){
        int k = d + ls[i].se - start - i - 1;
        if (k < 0) ans = max(ans, ls[i].fi);
        else{
            ans = max(ans, ls[i].fi + rs[k].fi);
        }
    }
    return ans;
}

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