Submission #116240

#	Time	Username	Problem	Language	Result	Execution time	Memory
116240		someone_aa	Holiday (IOI14_holiday)	C++17	24 / 100	99 ms	65536 KiB

holiday

#include <bits/stdc++.h>
//#include "holiday.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100500;
ll value[maxn], d;
int arr[maxn];

set<int>st;
map<int,int>ind;
int n, start, c;
ll dp[maxn];

struct node {
public:
    node *lc, *rc;
    ll cnt;
    ll sum;

    node(ll _cnt, ll _sum) {
        lc = rc = NULL;
        cnt = _cnt; sum = _sum;
    }
    node(node *a, node *b) {
        sum = a->sum + b->sum;
        cnt = a->cnt + b->cnt;
        lc = a;
        rc = b;
    }
};

node* prefix[maxn];


node* build(int li=0, int ri=n) {
    if(li == ri) return new node(0LL, 0LL);
    else {
        int mid = (li + ri) / 2;
        return new node(build(li, mid), build(mid+1, ri));
    }
}

node* update(node *curr, int pos, int sum_val, int li=0, int ri=n) {
    if(li == ri) {
        return new node(curr->cnt+1, curr->sum+sum_val);
    }
    else {
        int mid = (li + ri) / 2;

        if(pos <= mid)
            return new node(update(curr->lc, pos, sum_val, li, mid), curr->rc);
        else
            return new node(curr->lc, update(curr->rc, pos, sum_val, mid+1, ri));
    }
}

ll solve(node *l, node *r, int k, int li=0, int ri=n) {
    if(k == 0) return 0LL;
    ll total_cnt = r->cnt - l->cnt;
    ll total_sum = r->sum - l->sum;

    //cout<<"["<<li<<" "<<ri<<"] -> "<<total_cnt<<", "<<total_sum<<"\n";

    if(k == total_cnt) return total_sum;
    if(li == ri) return k * value[li];
    else {
        int mid = (li + ri) / 2;
        ll total = r -> rc -> cnt - l -> rc -> cnt;
        ll sum_total = r -> rc -> sum - l -> rc -> sum;
        if(total >= k) return solve(l->rc, r->rc, k, mid+1, ri);
        else return sum_total + solve(l->lc, r->lc, k-total, li, mid);
    }
}

void solvedp(int l=1, int r=start, int optl=start, int optr=n) {
    if(l > r) return;
    int mid = (l + r) / 2;

    // calculate dp[mid]
    dp[mid] = -1;
    int optmid = -1;
    for(int i=optl;i<=optr;i++) {
        ll walk = i - mid + min(start - mid, i - start);
        ll curr = solve(prefix[mid-1], prefix[i], max(0LL, c - walk));
        if(curr > dp[mid]) {
            dp[mid] = curr;
            optmid = i;
        }
    }

    solvedp(l, mid-1, optl, optmid);
    solvedp(mid+1, r, optmid, optr);
}

ll findMaxAttraction(int _n, int _start, int _c, int _attractions[]) {
    //ifstream fin("input.txt");
    n = _n;
    start = _start;
    c = _c;
    //cin>>n>>start>>c;
    start++;
    for(int i=0;i<n;i++) {
        arr[i] = _attractions[i];
        st.insert(arr[i]);
    }

    int br = 1;
    for(int i:st) {
        value[br] = i;
        ind[i] = br++;
    }
    d = br - 1;
    for(int i=n-1;i>=0;i--) {
        arr[i+1] = ind[arr[i]];
    }

    node *curr = build();
    prefix[0] = curr;
    for(int i=1;i<=n;i++) {
        curr = update(curr, arr[i], value[arr[i]]);
        prefix[i] = curr;
    }

    solvedp();
    ll result = 0LL;
    for(int i=1;i<=n;i++) {
        result = max(result, dp[i]);
    }
    return result;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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