oj.uz

Submission #14795

# Submission time Handle Problem Language Result Execution time Memory
14795 2015-06-24T08:07:36 Z ainta Holiday (IOI14_holiday) C++
30 / 100
 154 ms 6636 KB 
#include"holiday.h"
#include<stdio.h>
#include<algorithm>
#define SZ 131082
using namespace std;

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

int P, D, Num[101000];
long long Res;

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

void UDT(int a){
    while(a!=1){
        a>>=1;
        IT[a].S=IT[a+a].S+IT[a+a+1].S;
        IT[a].C=IT[a+a].C+IT[a+a+1].C;
    }
}
void On(int a){
    a=Num[a];
    IT[SZ+a].S=w[a].a,IT[SZ+a].C=1;
    UDT(SZ+a);
}
void Off(int a){
    a=Num[a];
    IT[SZ+a].S=0,IT[SZ+a].C=0;
    UDT(SZ+a);
}
long long Gap(int t){
    long long S=0;
    int nd = 1;
    while(nd<SZ){
        nd=nd+nd+1;
        if(IT[nd].C<=t){
            t-=IT[nd].C;
            S+=IT[nd].S;
            nd--;
        }
    }
    return S;
}

void Do1(int b, int e, int s, int l){
    if(b>e)return;
    int m = (b+e)>>1, i, x;
    long long M=0,S;
    for(i=m;i<=e;i++)On(i);
    for(i=s;i<=l;i++){
        On(i);
        S = Gap(D-(P-m)-(i-m));
        if(M<S)M=S,x=i;
    }
    Res=max(Res,M);
    if(b!=e){
        for(i=s;i<=l;i++)Off(i);
        Do1(b,m-1,s,x);
        for(i=m;i<=e;i++)Off(i);
        for(i=s;i<x;i++)On(i);
        Do1(m+1,e,x,l);
        for(i=s;i<x;i++)Off(i);
    }
    else{
        for(i=s;i<=l;i++)Off(i);
        for(i=m;i<=e;i++)Off(i);
    }
}

void Do2(int b, int e, int s, int l){
    if(b>e)return;
    int m = (b+e)>>1, i, x;
    long long M=0,S;
    for(i=b;i<=m;i++)On(i);
    for(i=l;i>=s;i--){
        On(i);
        S = Gap(D-(m-P)-(m-i));
        if(M<S)M=S,x=i;
    }
    Res=max(Res,M);
    if(b!=e){
        for(i=s;i<=l;i++)Off(i);
        Do2(m+1,e,x,l);
        for(i=b;i<=m;i++)Off(i);
        for(i=x+1;i<l;i++)On(i);
        Do2(b,m-1,s,x);
        for(i=x+1;i<l;i++)Off(i);
    }
    else{
        for(i=s;i<=l;i++)Off(i);
        for(i=b;i<=m;i++)Off(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);
    for(i=0;i<n;i++)Num[w[i].num]=i;
    P=start;
    Res=0;
    Do1(max(start-d/2,0),start,start,n-1);
    if(start)Do2(start,min(n-1,start+d/2),0,start-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 6636 KB Output is correct
3 Correct 0 ms 6632 KB Output is correct
4 Correct 0 ms 6636 KB Output is correct
5 Correct 0 ms 6632 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6628 KB Output is correct
2 Correct 24 ms 6628 KB Output is correct
3 Correct 28 ms 6632 KB Output is correct
4 Correct 28 ms 6628 KB Output is correct
5 Correct 33 ms 6632 KB Output is correct
6 Correct 19 ms 6628 KB Output is correct
7 Correct 24 ms 6632 KB Output is correct
8 Correct 8 ms 6632 KB Output is correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6632 KB Output is correct
2 Correct 4 ms 6632 KB Output is correct
3 Correct 0 ms 6628 KB Output is correct
4 Correct 10 ms 6628 KB Output is correct
5 Incorrect 9 ms 6628 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6632 KB Output is correct
2 Correct 42 ms 6632 KB Output is correct
3 Correct 138 ms 6632 KB Output is correct
4 Incorrect 8 ms 6632 KB Output isn't correct
5 Halted 0 ms 0 KB -