Submission #251357

#	Time	Username	Problem	Language	Result	Execution time	Memory
251357		Lawliet	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1116 ms	187568 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
 
const int MAXN = 200010;
 
int dx[] = { -1 , 1 , 0 , 0 };
int dy[] = { 0 , 0 , -1 , 1 };
 
char dir[] = { 'N' , 'S' , 'W' , 'E' };
 
int R, C;

class PersistentSegmentTree
{
	public:
 
		void copy(int node)
		{
			e.push_back( e[node] );
			d.push_back( d[node] );
			sum.push_back( sum[node] );
		}
 
		int update(int node, int l, int r, int i)
		{
			int newNode = ++cnt;
			copy( node );
 
			if( l == r )
			{
				sum[newNode]++;
				return newNode;
			}
 
			int m = ( l + r )/2;
 
			if( i <= m )
			{
				int aux = update( e[newNode] , l , m , i );
				e[newNode] = aux;
			}
			else
			{
				int aux = update( d[newNode] , m + 1 , r , i );
				d[newNode] = aux;
			}
 
			sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];

			return newNode;
		}

		void updateRoot() { root.push_back( root.back() ); }

		void update(int y)
		{
			if( y < 1 || C < y ) return;

			int r = update( root.back() , 1 , C , y );
			root.back() = r;
		}
 
		int query(int node, int l, int r, int i, int j)
		{
			if( node == 0 ) return 0;
			if( j < l || r < i ) return 0;
			if( i <= l && r <= j ) return sum[node];
 
			int m = ( l + r )/2;
 
			int sumLeft = query( e[node] , l , m , i , j );
			int sumRight = query( d[node] , m + 1 , r , i , j );
 
			return sumLeft + sumRight;
		}

		int query(int x1, int y1, int x2, int y2)
		{
			int ans = query( root[x2] , 1 , C , y1 , y2 );
			ans -= query( root[x1 - 1] , 1 , C , y1 , y2 );

			return ans;
		}
 
		PersistentSegmentTree() : cnt(1)
		{
			e.resize( 2 , 0 ); d.resize( 2 , 0 );
			sum.resize( 2 , 0 ); root.resize( 1 , 1 );
		}
 
	protected:
 
		int cnt;
 
		vector<int> e, d;
		vector<int> sum, root;
};
 
int minY, maxY;
int minX, maxX;
 
PersistentSegmentTree faces;
PersistentSegmentTree vertices;
PersistentSegmentTree edgesVert, edgesHor;

vector<int> sweepFaces[MAXN];
vector<int> sweepVertices[MAXN];
vector<int> sweepEdgesVert[MAXN], sweepEdgesHor[MAXN];
 
set<pii> river;
 
int conv(char a)
{
	for(int i = 0 ; i < 4 ; i++)
		if( a == dir[i] ) return i;
}
 
bool inside(int x, int y) { return ( river.find( { x , y } ) ) != river.end(); }
 
void init(int r, int c, int sr, int sc, int M, char *S) 
{
	R = r; C = c;
	river.insert( { sr , sc } );
 
	for(int i = 0 ; i < M ; i++)
	{
		int d = conv( S[i] );
		sr += dx[d]; sc += dy[d];
 
		river.insert( { sr , sc } );
	}
 
	maxX = -MAXN; minX = MAXN;
	maxY = -MAXN; minY = MAXN;
 
	for(auto it = river.begin() ; it != river.end() ; it++)
	{
		int x = it->first;
		int y = it->second;
 
		maxX = max( maxX , x ); minX = min( minX , x );
		maxY = max( maxY , y ); minY = min( minY , y );
 
		sweepVertices[x].push_back( y );

		sweepEdgesHor[x].push_back( y );
		sweepEdgesVert[x].push_back( y );
 
		if( !inside( x - 1 , y ) )
			sweepEdgesVert[x - 1].push_back( y );
 
		if( !inside( x , y - 1 ) )
			sweepEdgesHor[x].push_back( y - 1 );
 
		sweepFaces[x].push_back( y );
 
		if( !inside( x - 1 , y ) )
			sweepFaces[x - 1].push_back( y );
 
		if( !inside( x , y - 1 ) && !inside( x + 1 , y - 1 ) )
			sweepFaces[x].push_back( y - 1 );
 
		if( !inside( x , y - 1 ) && !inside( x - 1 , y ) && !inside( x - 1 , y - 1 ) )
			sweepFaces[x - 1].push_back( y - 1 );
	}

	for(int i = 1 ; i <= R ; i++)
	{
		faces.updateRoot(); vertices.updateRoot();
		edgesHor.updateRoot(); edgesVert.updateRoot();

		while( !sweepFaces[i].empty() )
		{
			faces.update( sweepFaces[i].back() );
			sweepFaces[i].pop_back();
		}

		while( !sweepVertices[i].empty() )
		{
			vertices.update( sweepVertices[i].back() );
			sweepVertices[i].pop_back();
		}

		while( !sweepEdgesVert[i].empty() )
		{
			edgesVert.update( sweepEdgesVert[i].back() );
			sweepEdgesVert[i].pop_back();
		}

		while( !sweepEdgesHor[i].empty() )
		{
			edgesHor.update( sweepEdgesHor[i].back() );
			sweepEdgesHor[i].pop_back();
		}
	}
}
 
int colour(int ar, int ac, int br, int bc) 
{
	lli N = br - ar + 1;
	lli M = bc - ac + 1;
 
	lli qtdVertices = N*M - vertices.query( ar , ac , br , bc );
 
	lli qtdEdges = 2*N*M - N - M;
	qtdEdges -= edgesHor.query( ar , ac , br , bc - 1 );
	qtdEdges -= edgesVert.query( ar , ac , br - 1 , bc );
 
	lli qtdFaces = (N - 1)*(M - 1);
	qtdFaces -= faces.query( ar , ac , br - 1 , bc - 1 );
 
	lli ans = qtdVertices - qtdEdges + qtdFaces;
 
	if( ar < minX && maxX < br && ac < minY && maxY < bc )
		ans++;
 
    return ans;
}

Compilation message (stderr)

rainbow.cpp: In function 'int conv(char)':
rainbow.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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