oj.uz

Submission #170496

# Submission time Handle Problem Language Result Execution time Memory
170496 2019-12-25T13:15:59 Z CaroLinda Holiday (IOI14_holiday) C++14
100 / 100
 836 ms 46700 KB 
#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 = true ;

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

	if( fim < ini  ) return ;

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

	for(int i = optmin ; i <= optmax  ; 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( max(1, start-d) ,start,start,n) ;
	ok=false ;
	calc(start,min(n, start+d),1,start) ;
	
	lp(i,1,start) resp[start] = max( resp[start] , seg.qry( rt[i-1] , rt[start] , 1 , n , d-abs(i-start) ) ) ;
	lp(i,start, n+1) resp[start] = max( resp[start] , seg.qry( rt[start-1] , rt[i] , 1 , n , d-abs(i-start) ) ) ;

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 45700 KB Output is correct
2 Correct 165 ms 45700 KB Output is correct
3 Correct 167 ms 45672 KB Output is correct
4 Correct 168 ms 45700 KB Output is correct
5 Correct 187 ms 42368 KB Output is correct
6 Correct 41 ms 11720 KB Output is correct
7 Correct 87 ms 22312 KB Output is correct
8 Correct 115 ms 26408 KB Output is correct
9 Correct 31 ms 8772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1520 KB Output is correct
2 Correct 5 ms 1648 KB Output is correct
3 Correct 5 ms 1648 KB Output is correct
4 Correct 8 ms 1540 KB Output is correct
5 Correct 9 ms 1268 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 4 ms 764 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 45636 KB Output is correct
2 Correct 169 ms 45576 KB Output is correct
3 Correct 150 ms 20088 KB Output is correct
4 Correct 9 ms 1520 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 824 ms 46700 KB Output is correct
9 Correct 836 ms 46604 KB Output is correct