Submission #42873

#	Time	Username	Problem	Language	Result	Execution time	Memory
42873		PowerOfNinjaGo	Holiday (IOI14_holiday)	C++14	47 / 100	5079 ms	52744 KiB

holiday

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "holiday.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
int *arr, N, st, D;
const int maxn = 1e5+5;
int rev[maxn];
int rnk[maxn];
struct node
{
    vi foo; vector< ll > qs;
    node *left, *right;
    node()
    {
        left = right = NULL;
    }
    int getNum(int x)
    {
        return ( (int) foo.size())-(lower_bound(foo.begin(), foo.end(), x)-foo.begin());
    }
    ll getSum(int x)
    {
        int k = lower_bound(foo.begin(), foo.end(), x)-foo.begin();
        return qs.back() - (k?qs[k-1]:0);
    }
    int askNum(int i, int j, int x, int L = 0, int R = N-1)
    {
        if(i> R || j< L) return 0LL;
        if(i<= L && R<= j)
        {
            return getNum(x);
        }
        int M = (L+R)/2;
        int a = left->askNum(i, j, x, L, M);
        int b = right->askNum(i, j, x, M+1, R);
        return a+b;
    }
    ll askSum(int i, int j, int x, int L = 0, int R = N-1)
    {
        if(i> R || j< L) return 0LL;
        if(i<= L && R<= j)
        {
            //printf("arrived %lld (%d) (%d, %d)\n", qs.back(), qs.size(), L, R);
            return getSum(x);
        }
        //printf("kuy%d %d %d %d\n", i, j, L, R);
        int M = (L+R)/2;
        ll a = left->askSum(i, j, x, L, M);
        ll b = right->askSum(i, j, x, M+1, R);
        return a+b;
    }
};
void merge(vi &A, vi &B, vi &C)
{
    int x = 0, y = 0;
    int n = B.size(), m = C.size();
    while(x< n && y< m)
    {
        if(B[x]< C[y]) A.pb(B[x++]);
        else A.pb(C[y++]);
    }
    while(x< n) A.pb(B[x++]);
    while(y< m) A.pb(C[y++]);
}
node *build(int L, int R)
{
    if(L == R)
    {
        node *ret = new node;
        ret->foo.pb(rev[L]);
        ret->qs.pb(arr[L]);
        return ret;
    }
    int M = (L+R)/2;
    node* ret = new node;
    ret->left = build(L, M);
    ret->right = build(M+1, R);
    merge(ret->foo, ret->left->foo, ret->right->foo);
    for(int i = 0; i< (int) ret->foo.size(); i++)
    {
        ret->qs.pb((ret->qs.empty()?0LL:ret->qs.back())+rnk[ret->foo[i]]);
    }
    //printf("%d to %d:\n", L, R);
    //for(int i = 0; i< (int) ret->foo.size(); i++) printf("%lld ", ret->qs[i]);
    //printf("(%d)\n", ret->qs.back());
    //printf("\n");
    return ret;
}
node *root;
ll sumK(int k, int a, int b)
{
    int tot = b-a+1;
    if(k>= tot) return root->askSum(a, b, -1);
    int lo = 0, hi = N-1;
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        //printf("askNum(%d, %d, %d) = %d\n", a, b, mid, root->askNum(a, b, mid));
        if(root->askNum(a, b, mid)<= k) hi = mid;
        else lo = mid+1;
    }
    //printf("lo is %d\n", lo);
    return root->askSum(a, b, lo);
}
ll solve(int L = 0, int R = st, int i = st, int j = N-1)
{
    if(L> R) return 0;
    int M = (L+R)/2;
    int opt = i;
    ll res = -4e18;
    for(int p = i; p<= j; p++)
    {
        int a = st-M, b = p-st;
        int del = min(a, b)*2+max(a, b);
        if(del>= D) break;
        ll here = sumK(D-del, M, p);
        //printf("sumK(%d %d %d) = %lld\n", D-del, M, p, here);
        if(here> res)
        {
            res = here;
            opt = p;
        }
    }
    //printf("%d\n", M);
    return max(max(res != -4e18?solve(L, M-1, i, opt):0, solve(M+1, R, opt, j)), res);
}
long long findMaxAttraction(int n, int start, int d, int attraction[])
{
    arr = attraction; N = n; st = start; D = d;
    vii foo;
    for(int i = 0; i< n; i++) foo.pb(ii(arr[i], i));
    sort(foo.begin(), foo.end());
    for(int i = 0; i< n; i++)
    {
        rev[foo[i].Y] = i;
        rnk[i] = foo[i].X;
    }
    root = build(0, n-1);
    //printf("it's %d\n", sumK(3, 1, 4));
    return solve();
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53