Submission #892642

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

holiday

#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int N = 1e5 + 5;

int n, d, start, a[N], ori[N], sz; long long ans = 0;
vector<int> val;
struct node{
    int cnt; long long sum;
    node *l, *r;

    node(){
        l = r = nullptr, cnt = sum = 0;
    }
};

node *root[N];

node *build(int l, int r){
    node *p = new node();
    if(l == r){
        return p;
    }
    int mid = (l + r) / 2;
    p -> l = build(l, mid);
    p -> r = build(mid + 1, r);
    return p;
}

node* upd(node *k, int tl, int tr, int i, int x){
    node *p = new node();
    if(tl == tr){
        p -> cnt = k -> cnt + 1;
        p -> sum = k -> sum + ori[tl];
        return p;
    }

    int mid = (tl + tr) / 2;
    if(i <= mid){
        p -> l = upd(k -> l, tl, mid, i, x);
        p -> r = k -> r;
    } else{
        p -> l = k -> l;
        p -> r = upd(k -> r, mid + 1, tr, i, x);
    }
    p -> cnt = p -> l -> cnt + p -> r -> cnt;
    p -> sum = p -> l -> sum + p -> r -> sum;
    return p;
}

long long query(node *l, node *r, int tl, int tr, int k){
    if(tl == tr){
        return 1LL * ori[tl] * min(k, r -> cnt - l -> cnt);
    }

    int mid = (tl + tr) / 2; long long ans = 0;

    if(r -> r -> cnt - l -> r -> cnt >= k){
        return query(l -> r, r -> r, mid + 1, tr, k);
    } else{
//        cout << ori[mid + 1] << " " << r -> r -> cnt - l -> r -> cnt << " " << r -> r -> sum - l -> r -> sum << endl;
        return r -> r -> sum - l -> r -> sum + query(l -> l, r -> l, tl, mid, k - (r -> r -> cnt - l -> r -> cnt));
    }
}
long long cost(int l, int start, int r){
    int queryop = d - (r - l + min(r - start, start - l));
//    cout << l << ' ' << start << " " << r << ' ' << queryop << " " << query(root[l - 1], root[r], 0, sz, queryop)<< endl;
    return query(root[l - 1], root[r], 0, sz, queryop);
}
void dnc(int l, int r, int optl, int optr){
    if(l > r) return;
    int mid = (l + r) / 2;
    pair<long long, int> best = {0, 0};
    for(int i = optl; i <= min(optr, mid); i++){
        best = max(best, {cost(i, start, mid), i});
    }
    ans = max(ans, best.first);
    dnc(l, mid - 1, optl, best.second);
    dnc(mid + 1, r, best.second, optr);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> start >> d;
    start++;
    for(int i = 1; i <= n; i++) cin >> a[i], val.push_back(a[i]);
    sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
    for(int i = 0; i < val.size(); i++) ori[i] = val[i];
    sz = val.size() - 1;
    root[0] = build(0, sz);
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
        root[i] = upd(root[i - 1], 0, sz, a[i], 1);
    }
    dnc(start, n, 1, start);
    cout << ans << endl;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int query(node*, node*, int, int, int)':
holiday.cpp:58:40: warning: unused variable 'ans' [-Wunused-variable]
   58 |     int mid = (tl + tr) / 2; long long ans = 0;
      |                                        ^~~
holiday.cpp: In function 'int main()':
holiday.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < val.size(); i++) ori[i] = val[i];
      |                    ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccbmsJ2o.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cca48vep.o:holiday.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccbmsJ2o.o: in function `main':
grader.cpp:(.text.startup+0xaf): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status