Submission #157481

#	Time	Username	Problem	Language	Result	Execution time	Memory
157481		jhnah917	Holiday (IOI14_holiday)	C++14	100 / 100	954 ms	41696 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, st, d;
p arr[101010]; //idx, cnt
ll ans = 0;

struct Seg{
    vector<p> tree[303030];
    int bias;

    void init(int n){
        for(bias=1; bias<=n; bias<<=1);
        for(int i=1; i<=n; i++){
            int x = bias | i;
            while(x){
                tree[x].push_back(arr[i]);
                x >>= 1;
            }
        }
        for(int i=bias-1; i>=1; i--){
            sort(all(tree[i]));
            for(int j=1; j<tree[i].size(); j++) tree[i][j].y += tree[i][j-1].y;
        }
    }

    p get(int node, int s, int e){
        p ret(0, 0);
        int l = lower_bound(tree[node].begin(), tree[node].end(), p(s, -1)) - tree[node].begin();
        int r = lower_bound(tree[node].begin(), tree[node].end(), p(e+1, -1)) - tree[node].begin();
        ret.x = r - l;
        if(r) ret.y = tree[node][r-1].y;
        if(l) ret.y-= tree[node][l-1].y;
        return ret;
    }

    ll query(int s, int e, int k){
        int x = 1; ll ret = 0; k++;
        while(x <= bias){
            auto tmp = get(x << 1, s, e);
            if(k <= tmp.x) x = (x << 1);
            else{
                x = (x << 1 | 1);
                k -= tmp.x;
                ret += tmp.y;
            }
        }
        return ret;
    }
}seg;

void dnc(int s, int e, int l, int r){
    if(s > e) return;
    int m = s + e >> 1;

    ll mx = -1, K = l;
    
    for(int i=l; i<=r; i++){
        int cnt = d - (i - m + min(i-st, st-m));
        if(cnt <= 0) continue;
        ll now = seg.query(m, i, min(cnt, i - m + 1));
        if(mx < now){
            mx = now; K = i;
        }
    }
    ans = max(ans, mx);
    dnc(s, m-1, l, K);
    dnc(m+1, e, K, r);
}

ll findMaxAttraction(int _n, int _st, int _d, int inp[]){
    n = _n; st = _st + 1; d = _d;
    for(int i=1; i<=n; i++) arr[i] = {i, inp[i-1]};
    sort(arr+1, arr+n+1, [&](p &a, p &b){
        return a.y > b.y;
    });
    seg.init(n);
    dnc(1, st, st, n);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'void Seg::init(int)':
holiday.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=1; j<tree[i].size(); j++) tree[i][j].y += tree[i][j-1].y;
                          ~^~~~~~~~~~~~~~~
holiday.cpp: In function 'void dnc(int, int, int, int)':
holiday.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~

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