oj.uz

Submission #881624

# Submission time Handle Problem Language Result Execution time Memory
881624 2023-12-01T15:53:46 Z Kubogi Holiday (IOI14_holiday) C++17
0 / 100
 26 ms 16332 KB 
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)

const int maxn = 1e5+4;
int n, s, t, a[maxn], mp[maxn];

struct Node {
    int sum = 0, cnt = 0;
} st[maxn*4];

Node operator +(const Node &A, const Node &B) {
    return {A.sum + B.sum, A.cnt + B.cnt};
}

void update(int id, int l, int r, int i, int v) {
    if (i < l || i > r) return;
    if (l == r) {
        st[id] = {v, 1};
        return;
    }

    int mid = (l+r)/2;
    update(id*2, l, mid, i, v);
    update(id*2+1, mid+1, r, i, v);

    st[id] = st[id*2] + st[id*2+1];
}

int walk(int k) {
    int id = 1, l = 0, r = n-1;
    if (st[1].cnt <= k) {
        return st[1].sum;
    }
    while (l < r) {
        int mid = (l+r)>>1;
        if (st[id*2].cnt >= k) {
            id = id*2;
            r = mid;
        } else {
            k -= st[id*2].cnt;
            id = id*2+1;
            l = mid+1;
        }
    }
    return st[id].sum;
}

int findMaxAttraction(int32_t _n, int32_t _s, int32_t _t, int32_t _a[]) {
    n = _n; s = _s; t = _t;
    for (int i = 0; i < n; i++) {
        a[i] = _a[i];
    }

    if (s == 0) {
        vector<pair<int, int>> V;
        for (int i = 0; i < n; i++) {
            V.push_back({a[i], i});
        }
        sort(V.rbegin(), V.rend());
        for (int i = 0; i < n; i++) {
            mp[V[i].second] = i;
        }

        int res = 0;
        for (int i = 0; t-i > 0; i++) {
            // move 1 -> i, get sum of t - i maximum
            update(1, 0, n-1, 1, a[i]);
            res = max(res, walk(t-i));
        }
        return res;
    }
    return -1;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2344 KB Output isn't correct
2 Halted 0 ms 0 KB -