Submission #251353

#	Time	Username	Problem	Language	Result	Execution time	Memory
251353		Lawliet	Land of the Rainbow Gold (APIO17_rainbow)	C++17	38 / 100	3123 ms	285068 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' };

class SparseSegmentTree
{
	public:

		void create()
		{
			e.push_back( 0 );
			d.push_back( 0 );
			sum.push_back( 0 );
		}

		int getLeft(int node)
		{
			if( e[node] == 0 )
				e[node] = ++cnt, create();

			return e[node];
		}

		int getRight(int node)
		{
			if( d[node] == 0 )
				d[node] = ++cnt, create();

			return d[node];
		}

		void update(int node, int l, int r, int i, int v)
		{
			if( i < l || r < i ) return;

			if( l == r )
			{
				sum[node] += v;
				return;
			}

			int m = ( l + r )/2;

			if( i <= m ) update( getLeft(node) , l , m , i , v );
			else update( getRight(node) , m + 1 , r , i , v );

			sum[node] = sum[ e[node] ] + sum[ d[node] ];
		}

		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;
		}

		SparseSegmentTree() : cnt(1) { create(); create(); }

	protected:

		int cnt;

		vector<int> sum;
		vector<int> e, d;
};

class FenwickTree
{
	public:

		void update(int x, int y, int v)
		{
			if( x == 0 ) return;

			for( ; x < MAXN ; x += x & -x)
				SEG[x].update( 1 , 1 , MAXN , y , v );
		}

		int query(int x, int y1, int y2)
		{
			int ans = 0;

			for( ; x > 0 ; x -= x & -x)
				ans += SEG[x].query( 1 , 1 , MAXN , y1 , y2 );

			return ans;
		}

		int query(int x1, int y1, int x2, int y2)
		{
			int ans = query( x2 , y1 , y2 );
			ans -= query( x1 - 1 , y1 , y2 );

			return ans;
		}

	protected:

		SparseSegmentTree SEG[MAXN];
};

int minY, maxY;
int minX, maxX;

FenwickTree faces;
FenwickTree vertices;
FenwickTree edgesVert, edgesHor;

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) 
{
	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 );

		vertices.update( x , y , 1 );

		edgesHor.update( x , y , 1 );
		edgesVert.update( x , y , 1 );

		if( !inside( x - 1 , y ) )
			edgesVert.update( x - 1 , y , 1 );

		if( !inside( x , y - 1 ) )
			edgesHor.update( x , y - 1 , 1 );

		faces.update( x , y , 1 );

		if( !inside( x - 1 , y ) )
			faces.update( x - 1 , y , 1 );

		if( !inside( x , y - 1 ) && !inside( x + 1 , y - 1 ) )
			faces.update( x , y - 1 , 1 );

		if( !inside( x , y - 1 ) && !inside( x - 1 , y ) && !inside( x - 1 , y - 1 ) )
			faces.update( x - 1 , y - 1 , 1 );
	}
}

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:132:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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