Submission #251354

#	Time	Username	Problem	Language	Result	Execution time	Memory
251354		Lawliet	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	2679 ms	227576 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/assoc_container.hpp> 

using namespace std;
using namespace __gnu_pbds; 
typedef pair<int,int> pii;
typedef long long int lli;
  
#define orderedSet tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int MAXN = 200010;

int dx[] = { -1 , 1 , 0 , 0 };
int dy[] = { 0 , 0 , -1 , 1 };

char dir[] = { 'N' , 'S' , 'W' , 'E' };

class FenwickTree
{
	public:

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

			for( ; x < MAXN ; x += x & -x)
				s[x].insert( y );
		}

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

			for( ; x > 0 ; x -= x & -x)
				ans += s[x].order_of_key( y2 + 1 ) - s[x].order_of_key( y1 );

			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:

		orderedSet s[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 );

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

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

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

		faces.update( x , y );

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

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

		if( !inside( x , y - 1 ) && !inside( x - 1 , y ) && !inside( x - 1 , y - 1 ) )
			faces.update( x - 1 , y - 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:68:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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