oj.uz

Submission #435094

# Submission time Handle Problem Language Result Execution time Memory
435094 2021-06-23T01:23:06 Z Lawliet Distributing Candies (IOI21_candies) C++17
29 / 100
 1751 ms 10484 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1361 ms 10480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 229 ms 5056 KB Output is correct
4 Correct 117 ms 5920 KB Output is correct
5 Correct 1661 ms 10480 KB Output is correct
6 Correct 1751 ms 10484 KB Output is correct
7 Correct 1685 ms 10480 KB Output is correct
8 Correct 1642 ms 10480 KB Output is correct
9 Correct 1305 ms 10468 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -