Submission #435094

#	Time	Username	Problem	Language	Result	Execution time	Memory
435094		Lawliet	Distributing Candies (IOI21_candies)	C++17	29 / 100	1751 ms	10484 KiB

candies

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

using namespace std;

const int MAXN = 200010;

int n, T;

int ord[MAXN];
int c[MAXN], v[MAXN];

vector<int> L, R, ans;
vector<int> setValue, lazy;

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

int getValue(int ind, int block)
{
	if( setValue[block] == -1 ) return lazy[block];
	if( setValue[block] == 0 ) return v[ind] + lazy[block];
	return c[ind] + lazy[block];
}

void rebuild()
{
	for(int i = 0 ; i < (int)L.size() ; i++)
		for(int j = L[i] ; j <= R[i] ; j++)
			v[j] = getValue( j , i );

	L.clear(); R.clear();
	setValue.clear(); lazy.clear();

	for(int i = 0 ; i < n ; i++)
	{
		if( i%T == 0 )
		{
			L.push_back( i ); R.push_back( i );
			setValue.push_back( 0 ); lazy.push_back( 0 );
		}
		else
			R.back()++;
	}
}

void getAnswer()
{
	rebuild();
	ans.resize( n , 0 );

	for(int i = 0 ; i < n ; i++)
		ans[ ord[i] ] = v[i];
}

void printBlocks()
{
	// for(int i = 0 ; i < (int)L.size() ; i++)
	// {
	// 	printf("Intervalo [%d,%d]\n",L[i],R[i]);
	// 	printf("Set %d  Lazy %d\n",setValue[i],lazy[i]);
	// 	printf("\n");
	// }

	// printf("---------------------------------------------\n");
}

vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v) 
{
    n = C.size();
    T = sqrt(n) + 1;

    for(int i = 0 ; i < n ; i++)
    	c[i] = C[i];

    iota( ord , ord + n , 0 );
    sort( ord , ord + n , cmp );

    sort( c , c + n );
    reverse( c , c + n );

    for(int i = 0 ; i < (int)l.size() ; i++)
    {
    	if( i%T == 0 )
    		rebuild();

    	printBlocks();

    	if( v[i] > 0 )
    	{
    		int blockBreak = -1;

    		for(int j = 0 ; j < (int)L.size() ; j++)
    			if( getValue( L[j] , j ) + v[i] < c[ L[j] ] ) blockBreak = j;

    		for(int j = blockBreak + 1 ; j < (int)L.size() ; j++)
    			setValue[j] = -2, lazy[j] = 0;

    		if( blockBreak == -1 )
    			continue;

    		int endBlock = L[blockBreak];

    		for(int j = L[blockBreak] + 1 ; j <= R[blockBreak] ; j++)
    			if( getValue( j , blockBreak ) + v[i] < c[j] ) endBlock = j;

    		for(int j = 0 ; j <= blockBreak ; j++)
    			lazy[j] += v[i];

    		if( endBlock == R[blockBreak] )
    			continue;

    		R.insert( R.begin() + blockBreak , endBlock );
    		L.insert( L.begin() + blockBreak + 1 , endBlock + 1 );

    		lazy.insert( lazy.begin() + blockBreak + 1 , 0 );
    		setValue.insert( setValue.begin() + blockBreak + 1 , -2 );
    	}
    	else
    	{
    		int blockBreak = -1;

    		for(int j = 0 ; j < (int)L.size() ; j++)
    			if( getValue( L[j] , j ) + v[i] > 0 ) blockBreak = j;

    		for(int j = blockBreak + 1 ; j < (int)L.size() ; j++)
    			setValue[j] = -1, lazy[j] = 0;

    		if( blockBreak == -1 )
    			continue;

    		int endBlock = L[blockBreak];

    		for(int j = L[blockBreak] + 1 ; j <= R[blockBreak] ; j++)
    			if( getValue( j , blockBreak ) + v[i] > 0 ) endBlock = j;

    		for(int j = 0 ; j <= blockBreak ; j++)
    			lazy[j] += v[i];

    		if( endBlock == R[blockBreak] )
    			continue;

    		R.insert( R.begin() + blockBreak , endBlock );
    		L.insert( L.begin() + blockBreak + 1 , endBlock + 1 );

    		lazy.insert( lazy.begin() + blockBreak + 1 , 0 );
    		setValue.insert( setValue.begin() + blockBreak + 1 , -1 );
    	}
    }

    getAnswer();
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33