oj.uz

Submission #15695

# Submission time Handle Problem Language Result Execution time Memory
15695 2015-07-15T13:44:52 Z ainta Holiday (IOI14_holiday) C++
100 / 100
 1208 ms 6636 KB 
#include"holiday.h"
#include<algorithm>
#define SZ 131072
using namespace std;

struct Order{
    int a, num;
    bool operator<(const Order &p)const{
        return a<p.a;
    }
}w[101000];

int Num[101000], D, st;

struct IdxTree{
    int num;
    long long S;
}IT[SZ+SZ];

long long Res;

void Ins(int nd, int b, int e, int x, int ck){
    if(b == e){
        if(ck == 1)IT[nd].num = 1, IT[nd].S = w[x].a;
        else IT[nd].num = 0, IT[nd].S = 0;
        return;
    }
    int m = (b+e)>>1;
    if(x <= m)Ins(nd*2,b,m,x,ck);
    else Ins(nd*2+1,m+1,e,x,ck);
    IT[nd].S=IT[nd*2].S+IT[nd*2+1].S;
    IT[nd].num=IT[nd*2].num+IT[nd*2+1].num;
}

void On(int x){
    Ins(1, 0, SZ-1, x, 1);
}
void Off(int x){
    Ins(1, 0, SZ-1, x, 0);
}

long long Gap(int nd, int b, int e, int k){
    if(IT[nd].num <= k)return IT[nd].S;
    int m = (b+e)>>1;
    if(IT[nd*2+1].num >= k)return Gap(nd*2+1,m+1,e,k);
    return IT[nd*2+1].S + Gap(nd*2,b,m,k-IT[nd*2+1].num);
}

void Do(int st, int b, int e, int s, int l){
    if(b>e || s>l)return;
    int i, mid = (b+e)>>1, t;
    for(i=mid;i<=e;i++){
        On(Num[i]);
    }
    long long M = -1, tp;
    int pv = s;
    for(i=s;i<=l;i++){
        t = D -(st - mid) - (i - mid);
        if(t<0)break;
        On(Num[i]);
        tp = Gap(1, 1, SZ, t);
        if(M < tp){
            M = tp, pv = i;
        }
    }
    Res = max(Res, M);
    for(i=s+1;i<=l;i++)Off(Num[i]);
    Do(st,b,mid-1,s,pv);
    for(i=mid;i<=e;i++)Off(Num[i]);
    for(i=s;i<pv;i++)On(Num[i]);
    Do(st,mid+1,e,pv,l);
    for(i=s;i<pv;i++)Off(Num[i]);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    int i;
    D = d;
    for(i=0;i<n;i++)w[i].a = attraction[i], w[i].num = i;
    sort(w,w+n);
    st = start;
    for(i=0;i<n;i++)Num[w[i].num]=i;
    Do(start, 0, start, start, n-1);
    for(i=0;i<n;i++)Num[n-1-w[i].num]=i;
    Do(n-1-start, 0, n-1-start, n-1-start, n-1);
    return Res;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 6632 KB Output is correct
2 Correct 290 ms 6628 KB Output is correct
3 Correct 324 ms 6632 KB Output is correct
4 Correct 296 ms 6632 KB Output is correct
5 Correct 381 ms 6636 KB Output is correct
6 Correct 104 ms 6628 KB Output is correct
7 Correct 202 ms 6628 KB Output is correct
8 Correct 244 ms 6632 KB Output is correct
9 Correct 64 ms 6628 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6632 KB Output is correct
2 Correct 4 ms 6632 KB Output is correct
3 Correct 9 ms 6632 KB Output is correct
4 Correct 23 ms 6632 KB Output is correct
5 Correct 17 ms 6632 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 3 ms 6636 KB Output is correct
8 Correct 6 ms 6632 KB Output is correct
9 Correct 6 ms 6628 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 6628 KB Output is correct
2 Correct 338 ms 6632 KB Output is correct
3 Correct 333 ms 6632 KB Output is correct
4 Correct 18 ms 6632 KB Output is correct
5 Correct 6 ms 6628 KB Output is correct
6 Correct 6 ms 6628 KB Output is correct
7 Correct 6 ms 6628 KB Output is correct
8 Correct 1208 ms 6632 KB Output is correct
9 Correct 1195 ms 6632 KB Output is correct