Submission #157479

#	Time	Username	Problem	Language	Result	Execution time	Memory
157479		jhnah917	Holiday (IOI14_holiday)	C++14	Compilation error	0 ms	0 KiB

holiday

#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<int, int> 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);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> st >> d; st++;
    for(int i=1; i<=n; i++) cin >> arr[i].y, arr[i].x = i;
    sort(arr+1, arr+n+1, [&](p &a, p &b){
        return a.y > b.y;
    });
    seg.init(n);
    dnc(1, st, st, n);
    cout << ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'void Seg::init(int)':
holiday.cpp:33: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:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~
/tmp/ccYIw1X7.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccVjlb6k.o:holiday.cpp:(.text.startup+0x0): first defined here
/tmp/ccYIw1X7.o: In function `main':
grader.cpp:(.text.startup+0x89): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status