Submission #131804

#	Time	Username	Problem	Language	Result	Execution time	Memory
131804		DodgeBallMan	Holiday (IOI14_holiday)	C++14	0 / 100	234 ms	49112 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

const int N = 1e5 + 10;
struct item{
    long long va;
    int sz, l, r;
}seg[20*N];

void newleaf( int now, long long va, int sz ) {
    seg[now].va = va, seg[now].sz = sz, seg[now].l = -1, seg[now].r = -1;
    return ;
}

void newpar( int now, int l, int r ) {
    seg[now].va = seg[l].va + seg[r].va, seg[now].sz = seg[l].sz + seg[r].sz, seg[now].l = l, seg[now].r = r;
    return;
}

int ver[N], cnt = 1;
unordered_map<long long, int> mp;
long long va[N], ans = -1LL;
int n, s, d;
vector<long long> coord;

int build( int l = 1, int r = n ) {
    if( l == r ) {
        int now = cnt;
        cnt++;
        newleaf( now, 0, 0 );
        return now;
    }
    int mid = ( l + r ) >> 1, now = cnt;
    cnt++;
    newpar( now, build( l, mid ), build( mid + 1, r ) );
    return now;
}

int update( int idx, long long va, int now, int l = 1, int r = n ) {
    if( l == r ) {
        int now = cnt;
        cnt++;
        newleaf( now, va, 1 );
        return now;
    }
    int mid = ( l + r ) >> 1, noww = cnt;
    cnt++;
    if( idx <= mid ) newpar( noww, update( idx, va, seg[now].l, l, mid ), seg[now].r );
    else newpar( noww, seg[now].l, update( idx, va, seg[now].r, mid + 1, r ) );
    return noww;
}

long long query( int a, int b, int idx, int l = 1, int r = n ) {
    if( idx <= 0 ) return 0LL;
    if( l == r ) return seg[b].va - seg[a].va;
    int mid = ( l + r ) >> 1;
    int diff = seg[seg[b].r].sz - seg[seg[a].r].sz;
    if( diff >= idx ) return query( seg[a].r, seg[b].r, idx, mid + 1, r );
    else return seg[seg[b].r].va - seg[seg[a].r].va + query( seg[a].l, seg[b].l, idx - diff, l, mid );
}

int cal( int l, int r ) {
    int ret = r - l;
    int x = abs( s - l ), y = abs( s - r );
    return ret + min( x, y );
}

int get( long long x ) { 
    mp[x]++;
    return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + mp[x]; 
} 

void solve( int l, int r, int lb, int rb ) {
    //printf("%d %d %d %d\n",l,r,lb,rb);
    if( l > r ) return ;
    int mid = ( l + r ) >> 1;
    long long nowans = -1LL, ind = lb;
    for( int i = max( lb, mid ) ; i <=  min( mid + d -1, rb ) ; i++ ) {
        int cos = cal( mid, i );
        nowans = max( nowans, va[i] );
        if( d - cos - 2 < 0 ) continue;
        long long temp = query( ver[mid], ver[i-1], d - cos - 2 );
        long long temp2 = va[mid] + ( ( i == mid ) ? 0 : va[i] );
        //printf("%lld %lld\n",temp,temp2);
        temp += temp2;
        if( temp > nowans ) ind = i, nowans = temp;
    }
    ans = max( ans, nowans );
    solve( l, mid - 1, lb, ind );
    solve( mid + 1, r, ind, rb );
}

long long findMaxAttraction( int N, int ST, int D, int ttt[] ) {
    s = ST + 1, d = D, n = N;
    for( int i = 0 ; i < n ; i++ ) { 
        va[i+1] = ( long long )ttt[i];
        coord.emplace_back( ttt[i] );
    }
    sort( coord.begin(), coord.end() );
    ver[0] = cnt;
    build();
    for( int i = 1 ; i <= n ; i++ ) {
        ver[i] = cnt;
        update( get( va[i] ), va[i], ver[i] );
    }
    //for( int i = 0 ; i <= n ; i++ ) printf("%d ",ver[i]);
    //printf("\n");
    solve( max( 1, s - d + 1 ), min( n, s + d - 1 ), 1, n );
    return ans;
}

// int main()
// {
//     int n, va[100], st, d;
//     scanf("%d %d %d",&n,&st,&d);
//     for( int i = 0 ; i < n ; i++ ) scanf("%d",&va[i]);
//     cout << findMaxAttraction( n, st, d, va );
// }

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