Submission #615892

#	Time	Username	Problem	Language	Result	Execution time	Memory
615892		Do_you_copy	Holiday (IOI14_holiday)	C++17	23 / 100	84 ms	65536 KiB

holiday

#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;

vector <ll> node;
struct __attribute__((packed)) TNode{
    TNode *lp, *rp;
    int val;
    ll sum;
    TNode(int _val, ll _sum) : lp(nullptr), rp(nullptr), val(_val), sum(_sum){}
    TNode(TNode* left, TNode* right){
        lp = left, rp = right;
        val = sum = 0;
        if (lp){
            val += lp->val;
            sum += lp->sum;
        }
        if (rp){
            val += rp->val;
            sum += rp->sum;
        }
    }
};

TNode* root[maxN];
ll p[maxN];
pll ls[maxD];
pll rs[maxD];
int Start;
TNode* build(int i, int l = 1, int r = node.size()){
    if (l == r){
        if (l == i) return new TNode(1, node[i - 1]);
        return new TNode(0, 0ll);
    }
    int mid = (l + r) / 2;
    return new TNode(build(i, l, mid), build(i, mid + 1, r));
}

TNode* update(TNode* id, int i, int l = 1, int r = node.size()){
    if (l == r){
        return new TNode(id->val + 1, id->sum + node[l - 1]);
    }
    int mid = (l + r) / 2;
    if (i <= mid) return new TNode(update(id->lp, i, l, mid), id->rp);
    else return new TNode(id->lp, update(id->rp, i, mid + 1, r));
}

ll get(TNode* id, int k, int l = 1, int r = node.size()){
    if (l == r){
        return k * node[l - 1];
    }
    int mid = (l + r) / 2;
    if (id->rp->val >= k) return get(id->rp, k, mid + 1, r);
    else return id->rp->sum + get(id->lp, k - 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(root[i], min(mid - (Start - i - 1), root[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;
    for (int i = s; i <= t; ++i){
        ll tem = get(root[i], min(mid - (i - Start), root[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;
    for (int i = 0; i < n; ++i){
        p[i + 1] = attraction[i];
        node.pb(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;
    root[start] = build(pos(p[start]));
    root[start - 1] = build(pos(p[start - 1]));
    for (int i = start + 1; i <= n; ++i){
        root[i] = update(root[i - 1], pos(p[i]));
    }
    for (int i = start - 2; i >= 1; --i){
        root[i] = update(root[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 - 1].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);

    }
    ofstream out("test.out");
    out << ans;
    out.close();
    return ans;
}

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