Submission #170492

#	Time	Username	Problem	Language	Result	Execution time	Memory
170492		CaroLinda	Holiday (IOI14_holiday)	C++14	23 / 100	493 ms	46652 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a; i <b;i++)
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define sz size()
#define debug printf
#define ll long long
#define pii pair<int,int>

const int MAXN = 1e5+10 ;
const ll inf = 1e18+10 ;

using namespace std ;

struct Seg 
{

	vector<int> e , d , qtd ;
	vector<ll> soma ;

	int create()
	{
		e.pb(0) ;
		d.pb(0) ;
		soma.pb(0LL) ;
		qtd.pb(0) ;
		return (int)(e.sz) - 1 ;
	}

	int create_and_copy(int pos)
	{
		e.pb(e[pos]) ;
		d.pb(d[pos]) ;
		soma.pb(soma[pos]) ;
		qtd.pb(qtd[pos]) ;
		return (int)(e.sz) -1 ;
	}

	int m(int l, int r) { return (l+r)>>1 ; }

	int upd(int pos, int l, int r, int idx, ll val)
	{

		int nv = create_and_copy(pos) ;

		soma[nv] += val ;
		qtd[nv] ++ ;

		if( l == r ) return nv ;

		int aux ;

		if( idx <= m(l,r) ) 
		{	
			aux = upd(e[nv], l, m(l,r) , idx, val) ;
			e[nv] = aux ;
		}
		else
		{
			aux = upd(d[nv], m(l,r)+1, r, idx, val) ;
			d[nv] = aux ;
		}

		return nv ;

	}

	ll qry(int rt1, int rt2 , int l , int r, int look)
	{


		if( l == r )
		{
			if( look  == 0 ) return 0LL ;
			return soma[ rt2 ] - soma[ rt1 ] ;
		}

		if( qtd[e[rt2]] - qtd[e[rt1]] >= look )
			return qry(e[rt1], e[rt2] , l, m(l,r) , look ) ;

		ll aux= qry( d[rt1] , d[rt2] , m(l,r)+1, r, look - qtd[ e[rt2] ] + qtd[ e[rt1] ] ) ;

		return aux + soma[e[rt2] ] - soma[ e[rt1] ] ;

	}

} ;

int n , start , d ;
int rt[MAXN] , a[MAXN] , idx[MAXN] , daysLeft[MAXN] ;
ll resp[MAXN] ;
Seg seg ;
bool ok = false ;

void calc(int ini , int fim , int optmin , int optmax )
{

	if( fim < ini ) return ;

	int mid = (ini+fim)>>1 , idxResp = -1 ;
	ll bestResp = -inf ;

	int pontaEsq, pontaDir ;

	if( mid < start ) pontaEsq = max(mid , optmin ) , pontaDir = optmax ;
	else pontaEsq = optmin , pontaDir = min(mid , optmax ) ;

	for(int i = pontaEsq ; i <= pontaDir ; i++ )
	{

		if( abs(mid - i) > daysLeft[mid] ) continue ;

		int ponta1 = min( i, min(start,mid) ) , ponta2 = max(i, max(start, mid));

		ll temp = seg.qry( rt[ponta1-1] , rt[ponta2] , 1 , n , daysLeft[mid] -abs(i-mid) ) ;

		if(temp > bestResp) bestResp = temp, idxResp = i ;

	}

	resp[mid] = bestResp ;

	calc( ini , mid-1 , optmin , idxResp ) ;
	calc( mid+1, fim , idxResp , optmax ) ;

}

bool cmp(int i, int j) { return a[i] > a[j] ; }

long long int findMaxAttraction(int N, int S, int D, int attraction[]) {

	n = N ; 
	start = S+1 ;
	d = D ;

	lp(i,1,n+1) 
	{
		a[i] = attraction[i-1] ;
		idx[i] = i ;
	}

	sort(idx+1, idx+1+n, cmp ) ;

	lp(i,1,n+1) attraction[ idx[i]-1 ] = i ;

	rt[0] = seg.create() ;

	lp(i,1,n+1) rt[i] = seg.upd( rt[i-1] , 1 , n , attraction[i-1] , a[i] ) ;
	lp(i,1,n+1) daysLeft[i]  = d - abs( i - start ) ;

	calc(1,n,1,n) ;

	lp(i,1,start) resp[start] = max( resp[start] , seg.qry( rt[i-1] , rt[start] , 1 , n , daysLeft[i] ) ) ;
	lp(i,start+1, n+1) resp[start] = max( resp[start] , seg.qry( rt[start-1] , rt[i] , 1 , n , daysLeft[i] ) ) ;

    return *max_element(resp+1, resp+1+n ) ;
}

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