oj.uz

Submission #251355

# Submission time Handle Problem Language Result Execution time Memory
251355 2020-07-21T01:04:50 Z Lawliet Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 412044 KB 
#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<pii, null_type,less<pii>, 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)
		{
			int t = x;

			for( ; x != 0 && x < MAXN ; x += x & -x)
				s[x].insert( { y , t } );
		}

		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 , 0 } ) - s[x].order_of_key( { y1 , 0 } );

			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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 76408 KB Output is correct
2 Correct 93 ms 80248 KB Output is correct
3 Correct 73 ms 76536 KB Output is correct
4 Correct 71 ms 76920 KB Output is correct
5 Correct 89 ms 81016 KB Output is correct
6 Correct 64 ms 75512 KB Output is correct
7 Correct 76 ms 75512 KB Output is correct
8 Correct 67 ms 75512 KB Output is correct
9 Correct 63 ms 75512 KB Output is correct
10 Correct 63 ms 75512 KB Output is correct
11 Correct 73 ms 77304 KB Output is correct
12 Correct 83 ms 78968 KB Output is correct
13 Correct 115 ms 82936 KB Output is correct
14 Correct 109 ms 84600 KB Output is correct
15 Correct 65 ms 75512 KB Output is correct
16 Correct 63 ms 75512 KB Output is correct
17 Correct 64 ms 75512 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 75512 KB Output is correct
2 Correct 64 ms 75512 KB Output is correct
3 Execution timed out 3097 ms 412044 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 75512 KB Output is correct
2 Execution timed out 3081 ms 321940 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 76408 KB Output is correct
2 Correct 93 ms 80248 KB Output is correct
3 Correct 73 ms 76536 KB Output is correct
4 Correct 71 ms 76920 KB Output is correct
5 Correct 89 ms 81016 KB Output is correct
6 Correct 64 ms 75512 KB Output is correct
7 Correct 76 ms 75512 KB Output is correct
8 Correct 67 ms 75512 KB Output is correct
9 Correct 63 ms 75512 KB Output is correct
10 Correct 63 ms 75512 KB Output is correct
11 Correct 73 ms 77304 KB Output is correct
12 Correct 83 ms 78968 KB Output is correct
13 Correct 115 ms 82936 KB Output is correct
14 Correct 109 ms 84600 KB Output is correct
15 Correct 65 ms 75512 KB Output is correct
16 Correct 63 ms 75512 KB Output is correct
17 Correct 64 ms 75512 KB Output is correct
18 Execution timed out 3075 ms 324464 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 76408 KB Output is correct
2 Correct 93 ms 80248 KB Output is correct
3 Correct 73 ms 76536 KB Output is correct
4 Correct 71 ms 76920 KB Output is correct
5 Correct 89 ms 81016 KB Output is correct
6 Correct 64 ms 75512 KB Output is correct
7 Correct 76 ms 75512 KB Output is correct
8 Correct 67 ms 75512 KB Output is correct
9 Correct 63 ms 75512 KB Output is correct
10 Correct 63 ms 75512 KB Output is correct
11 Correct 73 ms 77304 KB Output is correct
12 Correct 83 ms 78968 KB Output is correct
13 Correct 115 ms 82936 KB Output is correct
14 Correct 109 ms 84600 KB Output is correct
15 Correct 65 ms 75512 KB Output is correct
16 Correct 63 ms 75512 KB Output is correct
17 Correct 64 ms 75512 KB Output is correct
18 Execution timed out 3075 ms 324464 KB Time limit exceeded
19 Halted 0 ms 0 KB -