제출 #131806

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

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
//#define fuck 
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 );
//         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 );
// }

void solve(int l, int r, int optmin, int optmax)
{
	if( l > r ) return;
 
	int mid = (l + r)/2;
 
	int optInd = optmin;
	long long optAns = -1;
 
	for(int g = optmin ; g <= optmax ; g++)
	{
		int walkDays = (s - mid) + (g - mid);
 
		if(walkDays < 0) continue;
 
		long long curAns = query(ver[mid] , ver[g] , d - walkDays);
 
		if(curAns > optAns)
		{
			optInd = g;
			optAns = curAns;
		}
	}
 
	ans = max(ans , optAns);
 
	solve(l , mid - 1 , optmin , optInd);
	solve(mid + 1 , r , optInd , optmax);
}
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");
    // for( int i = max( 1, s - d + 1 ) ; i <= min( n, s + d - 1 ) ; i++ ) ans = max( ans, va[i]);
    // solve( max( 1, s - d + 1 ), min( n, s + d - 1 ), 1, n );
    s = n - s + 1;
    solve( 1, s, s, n );
    return ans;
}

#ifdef fuck
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 );
}
#endif

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