Submission #328199

#	Time	Username	Problem	Language	Result	Execution time	Memory
328199		CaroLinda	Land of the Rainbow Gold (APIO17_rainbow)	C++14	74 / 100	3075 ms	590932 KiB

rainbow

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

#define mk make_pair
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long

const int MAX = 2e5+10 ;

using namespace std ;

/*
I need two types of persistent segment trees:

* +1 in the opening and -1 in the closure
* +1 in everything
 
*/

struct persistentSeg
{

	//don't forget to create the dummy node

	vector<int> lef, rig , _sum ;
	int roots[MAX] ;
	
	int create()
	{
		lef.push_back(0) ;
		rig.push_back(0) ;
		_sum.push_back(0) ;

		return sz(lef) - 1 ;
	}

	int createAndCopy(int pos )
	{
		lef.push_back( lef[pos] ) ;
		rig.push_back( rig[pos] ) ;
		_sum.push_back( _sum[pos] ) ;

		return sz(lef) - 1 ;
	}

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

	int upd(int pos, int l, int r, int idx, int val )
	{
		int newPos = createAndCopy(pos) ;

		_sum[newPos] += val ;

		if( l== r ) return newPos ;

		if( idx <= m(l,r) ) 
		{
			int novo = upd(lef[newPos] , l , m(l,r) , idx, val ) ; 
			lef[newPos] = novo ;
		}
		else 
		{
			int novo = upd(rig[newPos] , m(l,r) + 1 , r , idx , val ) ; 
			rig[newPos] = novo ;			
		}

		return newPos ;

	}

	int qry(int pos, int l, int r, int beg, int en )
	{
		if( l > en || r < beg || !pos ) return 0 ;
		if( l >= beg && r <= en ) return _sum[pos] ;

		int al = qry(lef[pos] , l , m(l,r), beg, en  ) ;
		int ar = qry(rig[pos], m(l,r)+1, r, beg, en ) ;

		return al + ar ;
	}

} ;

struct Event
{

	//Type
	// 0 = opening
	// 1 = closure

	int r , c , type ;

	Event(int r = 0 , int c = 0 , int type = 0 ) : r(r)  ,c(c) , type(type) {} 
	
	bool operator < ( Event other ) const 
	{
		if( c != other.c ) return c < other.c ;
		return type < other.type ;
	}

	void print() { printf("%d %d %d\n", r, c , type ) ; }

} ;

int R, C ;
int maxR, minR, maxC, minC ;
persistentSeg vertices[2] , edges[2] ;

void init(int _R, int _C, int sr, int sc, int M, char *S) 
{
	
	R = _R ;
	C = _C ;

	vector< pii > serpentPath(1, make_pair(sr, sc) ) ;

	maxR = minR = sr ;
	maxC = minC = sc ;

	for(int i = 0 ; i < M ; i++ ) 
	{
		if( S[i] == 'N' ) sr-- ;
		if( S[i] == 'E' ) sc++ ;
		if(S[i] == 'S' ) sr++ ;
		if(S[i] == 'W' ) sc-- ;

		serpentPath.push_back(make_pair(sr, sc) ) ;

		maxR = max(maxR, sr ) ;
		minR = min(minR, sr) ;
		maxC = max(maxC, sc ) ;
		minC = min(minC, sc) ;

	}
	
	vector<int> freq[R+1] ;
	for(auto p : serpentPath ) freq[ p.first ].push_back( p.second ) ;

	vector<Event> sweep ;

	for(int i = 1 ; i <= R ; i++ )
	{
		if( sz(freq[i] ) == 0 )
		{
			sweep.push_back( Event(i , 1 , 0 ) ) ;
			sweep.push_back( Event(i, C , 1 ) ) ;	
			continue ;
		}
		
		sort(all(freq[i] ) ) ;
		freq[i].push_back(C+1) ;

		int formerColumn = 0 ;

		for(auto e : freq[i] )
		{
			if( formerColumn+1 <= e-1 )
			{
				sweep.push_back(Event(i, formerColumn+1, 0 ) ) ;
				sweep.push_back( Event(i, e-1, 1 ) ) ;
			}
				
			formerColumn =  e ;
		}

	}


	sort(all(sweep ) ) ;

	set<int> currentRows ;

	vertices[0].create() ; vertices[0].roots[0] = 0 ;
	vertices[1].create() ; vertices[1].roots[0] = 0 ;
	edges[0].create() ; edges[0].roots[0] = 0 ;
	edges[1].create() ; edges[1].roots[0] = 0 ;

	for(int i = 1 , ptr=0 ; i <= C ; i++ )
	{
		vertices[0].roots[i] = vertices[0].roots[i-1] ;
		vertices[1].roots[i] = vertices[1].roots[i-1] ;
		edges[0].roots[i] = edges[0].roots[i-1] ;
		edges[1].roots[i] = edges[1].roots[i-1] ;

		while( ptr < sz(sweep ) && sweep[ptr].c == i )
		{

			vertices[1].roots[i] = vertices[1].upd( vertices[1].roots[i] , 1 , R , sweep[ptr].r , 1 ) ;

			if(sweep[ptr].type == 0 )
			{
				vertices[0].roots[i] = vertices[0].upd( vertices[0].roots[i] , 1 , R , sweep[ptr].r , 1 ) ; 
				currentRows.insert( sweep[ptr].r ) ;

				auto it = currentRows.find( sweep[ptr].r ) ;

				if( it != currentRows.begin() ) 
				{
					it-- ;

					if( *it == sweep[ptr].r-1)
					{
						edges[0].roots[i] = edges[0].upd( edges[0].roots[i] , 1 , R  , *it , 1 ) ;
						edges[1].roots[i] = edges[1].upd( edges[1].roots[i] , 1 , R  , *it , 1 ) ;
					}
					it++ ;
				}
				it++ ;
				if(it != currentRows.end() && *it == sweep[ptr].r+1 )
				{
					edges[0].roots[i] = edges[0].upd( edges[0].roots[i] , 1 , R  , sweep[ptr].r , 1 ) ;
					edges[1].roots[i] = edges[1].upd( edges[1].roots[i] , 1 , R  , sweep[ptr].r , 1 ) ;					
				}

			}
			else
			{
				vertices[0].roots[i] = vertices[0].upd( vertices[0].roots[i] , 1 , R , sweep[ptr].r , -1 ) ;

				auto it = currentRows.find( sweep[ptr].r ) ;

				if( it != currentRows.begin() ) 
				{
					it-- ;
					if(*it == sweep[ptr].r-1 )
					{
						edges[0].roots[i] = edges[0].upd( edges[0].roots[i] , 1 , R  , *it , -1 ) ;
						edges[1].roots[i] = edges[1].upd( edges[1].roots[i] , 1 , R  , *it , 1 ) ;
					}
					it++ ;
				}
				it++ ;
				if(it != currentRows.end() && *it == sweep[ptr].r+1 )
				{
					edges[0].roots[i] = edges[0].upd( edges[0].roots[i] , 1 , R  , sweep[ptr].r , -1 ) ;
					edges[1].roots[i] = edges[1].upd( edges[1].roots[i] , 1 , R  , sweep[ptr].r , 1 ) ;					
				}
				it-- ;

				currentRows.erase(it) ;

			}                  

			ptr++ ;
		} 

	}

}

int colour(int ar, int ac, int br, int bc) 
{
	 
	int toSum = 0 ;

	if( ar < minR && br > maxR && ac < minC && bc > maxC )
	{
		ar = minR-1 ;
		br = maxR+1 ;
		ac = minC-1 ;
		bc = maxC+1 ;
		toSum = 1 ;	
	}

	//Count of vertices
	int z = vertices[0].qry(vertices[0].roots[bc], 1, R, ar, br ) ;
	int x = vertices[0].qry( vertices[0].roots[ac-1], 1 , R , ar , br ) ;
	int y = vertices[1].qry( vertices[1].roots[bc] , 1 , R , ar , br ) - vertices[1].qry( vertices[1].roots[ac-1] , 1 , R , ar , br ) ;

	y = (y - x - z )/2 ;

	int qtdVert = x + y + z ;

	//Count of edges
	br-- ;
	z = edges[0].qry(edges[0].roots[bc] , 1 , R , ar , br ) ;
	x = edges[0].qry( edges[0].roots[ac-1] , 1 , R , ar , br ) ;
	y = edges[1].qry( edges[1].roots[bc] , 1 , R , ar , br ) - edges[1].qry( edges[1].roots[ac-1] , 1 , R , ar , br ) ;
	y = (y-x-z)/2 ;

	int qtdEdges = x + y + z ;

	return qtdVert - qtdEdges + toSum ;

}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 0 / 26