Submission #116148

#	Time	Username	Problem	Language	Result	Execution time	Memory
116148		RezwanArefin01	Holiday (IOI14_holiday)	C++17	100 / 100	949 ms	9056 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int pos[N], p[N], a[N], n, d;

struct Node {
    ll sum; int cnt; 
    Node(ll sum = 0, int cnt = 0) : 
        sum(sum), cnt(cnt) {} 
} t[N << 2]; 

Node merge(Node a, Node b) { 
    return Node(a.sum + b.sum, a.cnt + b.cnt); 
}

void update(int node, int l, int r, int i, int x) {
    if(l == r) { 
        if(x >= 0) t[node] = Node(x, 1);
        else t[node] = Node(0, 0);
        return; 
    } int m = l + r >> 1; 
    if(i <= m) update(node << 1, l, m, i, x); 
    else update(node << 1 | 1, m + 1, r, i, x); 
    t[node] = merge(t[node << 1], t[node << 1 | 1]); 
}

ll query(int node, int k) {
    if(t[node].cnt <= k) return t[node].sum;
    if(t[node << 1].cnt >= k) return query(node << 1, k);
    else return query(node << 1 | 1, k - t[node << 1].cnt) + t[node << 1].sum;
}

ll ans; 
int start; 

void recurr(int l, int r, int b, int e) {
    if(l > r) return;
    int m = l + r >> 1, opt; 
    ll mx = 0;

    for(int i = l; i <= m; ++i)
        update(1, 0, n - 1, pos[i], a[i]);

    for(int i = e; i >= b; --i) {
        update(1, 0, n - 1, pos[i], a[i]); 
        int k = d - (m - start) - (m - i); 
        if(k <= 0) break; 
        ll now = query(1, k); 
        if(now > mx) mx = now, opt = i; 
    }
    if(mx > ans) ans = mx; 

    for(int i = e; i >= b; --i) 
        update(1, 0, n - 1, pos[i], -1); 
    recurr(m + 1, r, opt, e);

    for(int i = l; i <= m; ++i)
        update(1, 0, n - 1, pos[i], -1); 
    for(int i = e; i > opt; --i) 
        update(1, 0, n - 1, pos[i], a[i]); 
    recurr(l, m - 1, b, opt);

    for(int i = e; i > opt; --i) 
        update(1, 0, n - 1, pos[i], -1); 
}

void solve(int st) {
    iota(p, p + n, 0);
    sort(p, p + n, [](int i, int j) { return a[i] > a[j]; });
    for(int i = 0; i < n; ++i) pos[p[i]] = i;

    start = st; 
    recurr(st, min(n - 1, st + (d - 1) / 2), 0, st); 
}

ll findMaxAttraction(int _n, int _start, int _d, int _a[]) {
    n = _n, d = _d; 
    copy(_a, _a + n, a);

    solve(_start);
    reverse(a, a + n); 
    solve(n - _start - 1); 

    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void update(int, int, int, int, int)':
holiday.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int m = l + r >> 1; 
               ~~^~~
holiday.cpp: In function 'void recurr(int, int, int, int)':
holiday.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1, opt; 
             ~~^~~
holiday.cpp:65:11: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
     recurr(l, m - 1, b, opt);
     ~~~~~~^~~~~~~~~~~~~~~~~~
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: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53