oj.uz

답안 #881616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881616 2023-12-01T15:42:46 Z normankr07 휴가 (IOI14_holiday) C++17
0 / 100
 22 ms 11972 KB 
#include"holiday.h"
#include <bits/stdc++.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;
 
    Node operator+(const Node &A) const
    {
        return {sum + A.sum, cnt + A.cnt};
    }
} st[maxn * 4];
 
void update(int id, int l, int r, int i, int v)
{
    if (id < 0 || id >= maxn * 4)
    {
        cout << 962006;
        exit(0);
    }
    if (i < l || i > r)
        return;
    if (l == r)
    {
        // st[id] = {v, 1};
        return;
    }
    int mid = (l + r) >> 1;
    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];
}
Node get(int id, int l, int r, int a, int b)
{
    if (r < a || b < l)
        return {0, 0};
    if (a <= l && r <= b)
        return st[id];
 
    int mid = (l + r) >> 1;
    return get(id * 2, l, mid, a, b) + get(id * 2 + 1, mid + 1, r, a, b);
}
 
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, mp[i], a[i]);
            res = max(res, walk(t - i));
        }
        return res;
    }
    return -1;
}
 
#undef int

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 22 ms 11972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -