제출 #131753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131753		DodgeBallMan	휴가 (IOI14_holiday)	C++14	24 / 100	133 ms	65540 KiB

holiday

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

const int N = 1e5 + 10;
struct item{
    long long va;
    int sz;
    item *l, *r;
    item() { }
    item( long long va, int sz, item* l, item* r ) : va( va ), sz( sz ), l( l ), r( r ) { }
};

item* newleaf( long long va, int sz ) {
    return new item( va, sz, nullptr, nullptr );
}

item* newpar( item* l, item* r ) {
    return new item( l->va + r->va, l->sz + r->sz, l, r );
}

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

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

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

item* update( int idx, long long va, item* p, int l = 1, int r = n ) {
    //printf("%d %d %d %lld %d\n",l,r,idx,va,p->sz);
    if( l == r ) return newleaf( p->va + va, p->sz + 1 );
    int mid = ( l + r ) >> 1;
    if( idx <= mid ) return newpar( update( idx, va, p->l, l, mid ), p->r );
    else return newpar( p->l, update( idx, va, p->r, mid + 1, r ) );
}

long long query( item *a, item *b, int idx, int l = 1, int r = n ) {
    if( idx <= 0 ) return 0LL;
    if( l == r ) return b->va - a->va;
    int mid = ( l + r ) >> 1;
    int diff = b->r->sz - a->r->sz;
    //printf("L : %d R : %d diff : %d\n",l,r,diff);
    if( diff >= idx ) return query( a->r, b->r, idx, mid + 1, r );
    else return b->r->va - a->r->va + query( a->l, 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 );
}

long long solve( int l, int r, int lb, int rb ) {
    //printf("%d %d %d %d\n",l,r,lb,rb);
    if( l > r ) return 0LL;
    int mid = ( l + r ) >> 1;
    long long nowans = -1LL, ind = lb;
    for( int i = max( lb, mid ) ; i <=  min( mid + d - 2, rb ) ; i++ ) {
        int cos = cal( mid, i );
        if( d - cos - 2 < 0 ) continue;
        long long temp = query( ver[mid], ver[i-1], d - cos - 2 ) + va[mid] + va[i];
        //printf("L : %d R : %d va : %lld cost : %d\n",mid,i,temp,cos);
        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] );
    }
    if( d == 1 ) return va[s];
    sort( coord.begin(), coord.end() );
    ver[0] = build();
    for( int i = 1 ; i <= n ; i++ ) {
        ver[i] = update( get( va[i] ), va[i], ver[i-1] );
        //cout << i << endl;
    }
    //printf("%d %d %d\n",s,d,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 );
// }

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'long long int solve(int, int, int, int)':
holiday.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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