oj.uz

Submission #148132

# Submission time Handle Problem Language Result Execution time Memory
148132 2019-08-31T14:09:26 Z WhipppedCream Holiday (IOI14_holiday) C++17
24 / 100
 125 ms 65540 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#include "holiday.h"
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;
int cnt = 0;
struct node
{
    ll v;
    int v2;
    node *left, *right;
    node(ll a, int a2, node *b, node *c)
    {
        v = a; v2 = a2;
        left = b; right = c;
    }
    node* update(int L, int R, int x, int dx)
    {
        //printf("%d %d %d\n", L, R, x);
        if(L> x || R< x) return this;
        if(L == x && x == R)
        {
            cnt++;
            return new node(this->v+dx, this->v2+1, NULL, NULL);
        }
        int M = (L+R)/2;
        cnt++;
        return new node(this->v+dx, this->v2+1, this->left->update(L, M, x, dx), this->right->update(M+1, R, x, dx));
    }
};
node *zero;
const int maxn = 1e5+5;
node *val[maxn];
int rev[maxn];
ll tahm(node *va, node *vb, int k)
{
    //printf("ei (%lld-%lld) with (%lld-%lld)\n", a->v, b->v, (va->v), (vb->v));
    if(va->v2 - vb->v2 <= k) return va->v - vb->v;
    int x = va->right->v2 - vb->right->v2;
    //printf("yoyo %d\n", x);
    if(k<= x) return tahm(va->right, vb->right, k);
    return (va->right->v - vb->right->v) + tahm(va->left, vb->left, k-x);
}
ll sumK(int k, int a, int b)
{
    return tahm(val[b], a?val[a-1]:zero, k);
}
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;
        }
    }
    return max(max(solve(L, M-1, i, opt), 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;
    zero = new node(0, 0, NULL, NULL);
    zero->left = zero->right = zero;
    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;
    for(int i = 0; i< n; i++)
    {
        //printf("(%d)\n", rev[i]);
        val[i] = (i?val[i-1]:zero)->update(0, n-1, rev[i], arr[i]);
    }
    //printf("kuy %lld\n", val[n-1]->v);
    //printf("%d\n", sizeof(node));
    //printf("created %d nodes\n", cnt);
    return solve();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2296 KB Output is correct
2 Correct 5 ms 2168 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 7 ms 2040 KB Output is correct
5 Correct 6 ms 2168 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 125 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -