oj.uz

Submission #636348

# Submission time Handle Problem Language Result Execution time Memory
636348 2022-08-28T23:10:14 Z SirCovidThe19th Holiday (IOI14_holiday) C++17
100 / 100
 515 ms 10552 KB 
#include <bits/stdc++.h>
using namespace std; 

#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 * 3], bit[mx][2];

void upd(int i, int type){ 
    for (int j = pos[i]; j < mx; j += j & (-j))
        bit[j][0] += type * A[i], bit[j][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 or distL > distR) return;
    for (int i = distL; i <= distR; i++) upd(i, -1);

    int midD = (l + r) / 2, stopMid = -1;
    for (int stop = distL; stop <= distR; stop++){
        int visit = midD - (stop - st) * (rep ? 2 : 1);
        upd(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(i, -1);
    dnq(l, midD - 1, distL, stopMid, dir, rep);
    
    for (int i = stopMid + 1; i <= distR; i++) upd(i, 1);
    dnq(midD + 1, r, stopMid, distR, dir, rep);
}
void work(int start, int tmpA[], bool dir, bool rep){
    for (int i = 0; i < n; i++){
        A[i] = tmpA[i];
        S[i] = {tmpA[i], i};
    }
    sort(S, S + n, greater<pair<int, int>>());
    for (int i = 0; i < n; i++) pos[S[i].second] = i + 1; //BIT has to be 1 indexed

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

    reverse(tmpA, tmpA + n);
    work(n - start - 1, tmpA, 1, 0);
    work(n - start, 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]});
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 8644 KB Output is correct
2 Correct 402 ms 8620 KB Output is correct
3 Correct 443 ms 8668 KB Output is correct
4 Correct 402 ms 8760 KB Output is correct
5 Correct 498 ms 6968 KB Output is correct
6 Correct 188 ms 7236 KB Output is correct
7 Correct 283 ms 5248 KB Output is correct
8 Correct 331 ms 5292 KB Output is correct
9 Correct 155 ms 8248 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2516 KB Output is correct
2 Correct 13 ms 2464 KB Output is correct
3 Correct 13 ms 2420 KB Output is correct
4 Correct 13 ms 2388 KB Output is correct
5 Correct 12 ms 2388 KB Output is correct
6 Correct 4 ms 2296 KB Output is correct
7 Correct 4 ms 2260 KB Output is correct
8 Correct 5 ms 2260 KB Output is correct
9 Correct 5 ms 2260 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 9820 KB Output is correct
2 Correct 501 ms 10552 KB Output is correct
3 Correct 176 ms 3664 KB Output is correct
4 Correct 11 ms 2396 KB Output is correct
5 Correct 4 ms 2260 KB Output is correct
6 Correct 4 ms 2260 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 509 ms 6224 KB Output is correct
9 Correct 515 ms 6216 KB Output is correct