Submission #636338

#	Time	Username	Problem	Language	Result	Execution time	Memory
636338		SirCovidThe19th	휴가 (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

holiday

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

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long

const int mx = 1e5 + 5;

int n, d, st, pos[mx], A[mx]; pair<int, int> S[mx]; ll ans, F[2][2][mx], bit[mx][2];

void upd(int i, int type){
    int val = S[i].first;
    for (; i < mx; i += i & (-i)) 
        bit[i][0] += type * val, bit[i][1] += type;
}
ll qry(int k){
    ll ret = 0;
    for (int pw = (1 << 17), pos = 0; pw; pw /= 2)
        if (pos + pw < mx and bit[pos + pw][1] <= k){
            pos += pw; 
            ret += bit[pos][0];
            k -= bit[pos][1];
        }
    return ret;
}
void dnq(int l, int r, int distL, int distR, bool dir, bool rep){
    if (l > r) return;
    for (int i = distL; i <= distR; i++) upd(pos[i], -1);

    int midD = (l + r) / 2, stopMid;
    for (int stop = distL; stop <= distR; stop++){
        int visit = midD - (stop - st) * (rep ? 2 : 1);
        upd(pos[stop], 1);
        if (visit < 0) continue;

        ll val = qry(visit);
        if (val >= F[dir][rep][midD]){
            F[dir][rep][midD] = val;
            stopMid = stop;
        }
    }
    for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], -1);
    dnq(l, midD - 1, distL, stopMid, dir, rep);
    
    for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], 1);
    dnq(midD + 1, r, stopMid, distR, dir, rep);
}
void work(int start, vector<int> tmpA, bool dir, bool rep){
    for (int i = 0; i < n; i++){
        A[i + 1] = tmpA[i];
        S[i + 1] = {tmpA[i], i + 1};
    }
    sort(S + 1, S + n + 1, greater<pair<int, int>>());
    for (int i = 1; i <= n; i++) pos[S[i].second] = i;

    memset(bit, 0, sizeof(bit));
    for (int i = start; i <= n; i++) upd(pos[i], 1);
    
    st = start;
    dnq(0, d, start, n, dir, rep);
}
ll findMaxAttraction(int tmpN, int start, int tmpD, vector<int> tmpA){
    n = tmpN; d = tmpD; start++;
    work(start, tmpA, 0, 0);
    work(start + 1, tmpA, 0, 1);

    reverse(tmpA.begin(), tmpA.end());
    work(n - start + 1, tmpA, 1, 0);
    work(n - start + 2, tmpA, 1, 1);
    
    for (int i = 0; i <= d - 2; i++)
        ans = max({ans, F[0][1][i] + F[1][0][d - i - 2], F[1][1][i], F[0][0][d - i - 2]});
    
    return max({ans, F[0][0][d], F[1][0][d]});
}

Compilation message (stderr)

holiday.cpp: In function 'void dnq(int, int, int, int, bool, bool)':
holiday.cpp:42:14: warning: 'stopMid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |     for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], -1);
      |              ^
/usr/bin/ld: /tmp/ccvgdEUb.o: in function `main':
grader.cpp:(.text.startup+0xaf): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status