oj.uz

Submission #15693

# Submission time Handle Problem Language Result Execution time Memory
15693 2015-07-15T13:35:48 Z ainta Holiday (IOI14_holiday) C++
100 / 100
 1070 ms 6624 KB 
#include"holiday.h"
#include<algorithm>
using namespace std;
#define SZ 131072
#define N_ 100010
long long Res;
struct A{
    int a, num;
    bool operator <(const A &p)const{
        return a < p.a;
    }
}ord[N_];
struct ST{
    long long Sum;
    int C;
}IT[SZ*2+2];
int num[N_], N;
void Ins(int node, int b, int e, int x, int ck){
    if (b == e){
        if (ck == IT[node].C)return;
        if (ck){
            IT[node].C = 1;
            IT[node].Sum = ord[b].a;
        }
        else{
            IT[node].C = 0, IT[node].Sum = 0;
        }
        return;
    }
    int m = (b + e) >> 1;
    if (x <= m)Ins(node * 2, b, m, x, ck);
    else Ins(node * 2 + 1, m + 1, e, x, ck);
    IT[node].Sum = IT[node * 2].Sum + IT[node * 2 + 1].Sum;
    IT[node].C = IT[node * 2].C + IT[node * 2 + 1].C;
}
long long Gap(int node, int x){
    if (IT[node].C <= x)return IT[node].Sum;
    if (IT[node * 2 + 1].C >= x) return Gap(node * 2 + 1, x);
    else return IT[node * 2 + 1].Sum + Gap(node * 2, x - IT[node * 2 + 1].C);
}
void DP(int st, int b, int e, int s, int l, int d){
    if (b > e)return;
    int m = (b + e) >> 1, i, t, x;
    long long M = 0, S;
    for (i = m; i <= e; i++)
        Ins(1, 0, SZ-1, num[i], 1);
    for (i = s; i <= l; i++){
        Ins(1, 0, SZ-1, num[i], 1);
        t = d - st - i + m + m;
        if (t <= 0)break;
        S = Gap(1, t);
        if (M < S){
            M = S, x = i;
        }
    }
    if (Res < M)Res = M;
    for (i = s; i <= l; i++)Ins(1, 0, SZ-1, num[i], 0);
    DP(st, b, m - 1, s, x, d);
    for (i = m; i <= e; i++)Ins(1, 0, SZ-1, num[i], 0);
    for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 1);
    DP(st, m + 1, e, x, l, d);
    for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 0);
}
void Do(int st, int d){
    int i;
    DP(st, max(0, st - (d-1)/2), st, st, N - 1, d);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    int i;
    N = n;
    for (i = 0; i < n; i++){
        ord[i].a = attraction[i];
        ord[i].num = i;
    }
    sort(ord, ord + n);
    for (i = 0; i < n; i++)num[ord[i].num] = i;
    Do(start, d);
    for (i = 0; i < n; i++)num[n - 1 - ord[i].num] = i;
    Do(n - 1 - start, d);
    return Res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6624 KB Output is correct
2 Correct 0 ms 6620 KB Output is correct
3 Correct 0 ms 6620 KB Output is correct
4 Correct 0 ms 6620 KB Output is correct
5 Correct 0 ms 6620 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 6620 KB Output is correct
2 Correct 752 ms 6620 KB Output is correct
3 Correct 341 ms 6620 KB Output is correct
4 Correct 301 ms 6620 KB Output is correct
5 Correct 290 ms 6616 KB Output is correct
6 Correct 108 ms 6616 KB Output is correct
7 Correct 186 ms 6616 KB Output is correct
8 Correct 187 ms 6624 KB Output is correct
9 Correct 75 ms 6620 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6624 KB Output is correct
2 Correct 9 ms 6616 KB Output is correct
3 Correct 9 ms 6620 KB Output is correct
4 Correct 19 ms 6616 KB Output is correct
5 Correct 21 ms 6620 KB Output is correct
6 Correct 4 ms 6624 KB Output is correct
7 Correct 5 ms 6620 KB Output is correct
8 Correct 5 ms 6624 KB Output is correct
9 Correct 5 ms 6616 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 6624 KB Output is correct
2 Correct 342 ms 6620 KB Output is correct
3 Correct 234 ms 6616 KB Output is correct
4 Correct 15 ms 6620 KB Output is correct
5 Correct 5 ms 6620 KB Output is correct
6 Correct 5 ms 6620 KB Output is correct
7 Correct 5 ms 6624 KB Output is correct
8 Correct 1070 ms 6616 KB Output is correct
9 Correct 1058 ms 6616 KB Output is correct