Submission #116089

#	Time	Username	Problem	Language	Result	Execution time	Memory
116089		someone_aa	Holiday (IOI14_holiday)	C++17	0 / 100	30 ms	9564 KiB

holiday

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

class node {
public:
    ll sum, cnt, lb, rb;
    node *leftchild, *rightchild;

    node(ll _sum, ll _cnt) {
        sum = _sum;
        cnt = _cnt;
    }
    node(node *a, node *b) {
        leftchild = a;
        rightchild = b;

        sum = a->sum + b->sum;
        cnt = a->cnt + b->cnt;
    }
};

node* build(int li=1, int ri=d) {
    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, ll uind, ll uval, int li=1, int ri=d) {
    if(li == ri) {
        return new node(curr->sum + uval, curr->cnt + 1);
    }
    else {
        int mid = (li + ri) / 2;

        if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild);
        else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri));
    }
}

ll solve(node *p, node *pm, ll k, int li=1, int ri=d) {
    ll total = p->cnt - pm->cnt;

    if(total < k) return (p->sum - pm->sum);

    if(li == ri) {
        return k * value[li];
    }
    else {
        int mid = (li + ri) / 2;

        ll total_right = p->rightchild->cnt - pm->rightchild->cnt;
        if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri);
        else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total, li, mid);
    }
}

node *prefix[maxn];
set<int>st;
map<int,int>ind;

long long int findMaxAttraction(int n, int start, int money, int attraction[]) {
    for(int i=0;i<n;i++) {
        st.insert(attraction[i]);
    }
    
    int br = 1;
    for(int i:st) {
        value[br] = i;
        ind[i] = br++;
    }

    d = br - 1;
    cout<<"Done preprocessing\n";
    
    for(int i=n-1;i>=0;i--) {
        arr[i+1] = ind[attraction[i]];
    }
    for(int i=1;i<=n;i++) {
        cout<<arr[i]<<" ";
    } cout<<"\n";

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

    cout<<solve(prefix[4], prefix[1], 2)<<"\n";
    return 0;
}

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: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53