oj.uz

답안 #285762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285762 2020-08-29T14:46:49 Z Kastanda 휴가 (IOI14_holiday) C++11
100 / 100
 815 ms 7536 KB 
// M
#include<bits/stdc++.h>
#include"holiday.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 100005;
int n, st, d, A[N], Id[N], C[N * 4];
ll SM[N * 4];
vector < int > U;
ll MX;
void AddSeg(int i, int val, int id = 1, int l = 0, int r = (int)U.size())
{
        C[id] += val;
        SM[id] += (ll)val * U[i];
        if (r - l < 2)
                return ;
        if (i < md)
                AddSeg(i, val, lc, l, md);
        else
                AddSeg(i, val, rc, md, r);
}
ll GetSeg(int &k, int id = 1, int l = 0, int r = (int)U.size())
{
        if (k <= 0)
                return 0LL;
        if (C[id] <= k)
                return k -= C[id], SM[id];
        if (r - l < 2)
        {
                ll rt = (ll)U[l] * k;
                k = 0;
                return rt;
        }
        ll rt = GetSeg(k, rc, md, r);
        rt += GetSeg(k, lc, l, md);
        return rt;
}
inline void Add(int i, int val)
{
        AddSeg(Id[i], val);
}
ll Get(int k)
{
        int kk = k;
        return GetSeg(kk);
}
void Solve(int l, int r, int le, int ri)
{
        if (r < l)
                return ;
        int opt = -1;
        // [le, l) is added.
        for (int i = l; i <= md; i ++)
                Add(i, 1);
        ll Mx = 0;
        for (int i = le; i <= ri; i ++)
        {
                ll val = Get(d - (md - st + md - i));
                if (Mx <= val)
                        Mx = val, opt = i;
                Add(i, -1);
        }
        MX = max(MX, Mx);
        // (ri, md]
        for (int i = opt; i <= ri; i ++)
                Add(i, 1);
        // [opt, md]
        Solve(md + 1, r, opt, ri);
        for (int i = le; i < opt; i ++)
                Add(i, 1);
        // [le, md]
        for (int i = l; i <= md; i ++)
                Add(i, -1);
        // [le, l)
        Solve(l, md - 1, le, opt);
}

ll findMaxAttraction(int _n, int _start, int _d, int attraction[])
{
        n = _n; st = _start; d = _d;
        for (int i = 0; i < n; i ++)
                A[i] = attraction[i], U.push_back(A[i]);

        sort(U.begin(), U.end());
        U.resize(unique(U.begin(), U.end()) - U.begin());
        for (int i = 0; i < n; i ++)
                Id[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin();
        MX = 0;
        for (int w = 0; w <= 1; w ++)
        {
                memset(C, 0, sizeof(C));
                memset(SM, 0, sizeof(SM));
                for (int i = st; i < n; i ++)
                        Add(i, 1), MX = max(MX, Get(d - (i - st)));
                memset(C, 0, sizeof(C));
                memset(SM, 0, sizeof(SM));
                // Adding [le, l) :
                for (int i = 0; i < st; i ++)
                        Add(i, 1);
                Solve(st, n - 1, 0, st - 1);
                reverse(A, A + n);
                reverse(Id, Id + n);
                st = n - 1 - st;
        }
        return MX;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6776 KB Output is correct
2 Correct 29 ms 6648 KB Output is correct
3 Correct 31 ms 6776 KB Output is correct
4 Correct 36 ms 6776 KB Output is correct
5 Correct 111 ms 6648 KB Output is correct
6 Correct 35 ms 5632 KB Output is correct
7 Correct 79 ms 6012 KB Output is correct
8 Correct 75 ms 6140 KB Output is correct
9 Correct 25 ms 5504 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 14 ms 5120 KB Output is correct
5 Correct 12 ms 5120 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 6680 KB Output is correct
2 Correct 153 ms 6648 KB Output is correct
3 Correct 290 ms 5884 KB Output is correct
4 Correct 14 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 815 ms 7536 KB Output is correct
9 Correct 794 ms 7536 KB Output is correct