oj.uz

Submission #251353

# Submission time Handle Problem Language Result Execution time Memory
251353 2020-07-21T00:50:59 Z Lawliet Land of the Rainbow Gold (APIO17_rainbow) C++17
38 / 100
 3000 ms 285068 KB 
#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

rainbow.cpp: In function 'int conv(char)':
rainbow.cpp:132: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 289 ms 138364 KB Output is correct
2 Correct 297 ms 138488 KB Output is correct
3 Correct 288 ms 138388 KB Output is correct
4 Correct 301 ms 138340 KB Output is correct
5 Correct 307 ms 138532 KB Output is correct
6 Correct 291 ms 138360 KB Output is correct
7 Correct 261 ms 138104 KB Output is correct
8 Correct 265 ms 138100 KB Output is correct
9 Correct 261 ms 138136 KB Output is correct
10 Correct 263 ms 138104 KB Output is correct
11 Correct 289 ms 138488 KB Output is correct
12 Correct 292 ms 138488 KB Output is correct
13 Correct 303 ms 138616 KB Output is correct
14 Correct 310 ms 138740 KB Output is correct
15 Correct 300 ms 138104 KB Output is correct
16 Correct 268 ms 138104 KB Output is correct
17 Correct 259 ms 138192 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 138104 KB Output is correct
2 Correct 259 ms 138192 KB Output is correct
3 Correct 2541 ms 245068 KB Output is correct
4 Execution timed out 3123 ms 285068 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 138104 KB Output is correct
2 Correct 1557 ms 225412 KB Output is correct
3 Correct 1541 ms 274424 KB Output is correct
4 Correct 1698 ms 269620 KB Output is correct
5 Correct 1271 ms 231508 KB Output is correct
6 Correct 473 ms 144728 KB Output is correct
7 Correct 594 ms 150392 KB Output is correct
8 Execution timed out 3076 ms 225888 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 138364 KB Output is correct
2 Correct 297 ms 138488 KB Output is correct
3 Correct 288 ms 138388 KB Output is correct
4 Correct 301 ms 138340 KB Output is correct
5 Correct 307 ms 138532 KB Output is correct
6 Correct 291 ms 138360 KB Output is correct
7 Correct 261 ms 138104 KB Output is correct
8 Correct 265 ms 138100 KB Output is correct
9 Correct 261 ms 138136 KB Output is correct
10 Correct 263 ms 138104 KB Output is correct
11 Correct 289 ms 138488 KB Output is correct
12 Correct 292 ms 138488 KB Output is correct
13 Correct 303 ms 138616 KB Output is correct
14 Correct 310 ms 138740 KB Output is correct
15 Correct 300 ms 138104 KB Output is correct
16 Correct 268 ms 138104 KB Output is correct
17 Correct 259 ms 138192 KB Output is correct
18 Correct 2429 ms 169916 KB Output is correct
19 Correct 725 ms 143992 KB Output is correct
20 Correct 666 ms 142072 KB Output is correct
21 Correct 659 ms 142328 KB Output is correct
22 Correct 742 ms 143484 KB Output is correct
23 Correct 708 ms 144120 KB Output is correct
24 Correct 680 ms 142080 KB Output is correct
25 Correct 697 ms 142712 KB Output is correct
26 Correct 759 ms 143484 KB Output is correct
27 Correct 1146 ms 155660 KB Output is correct
28 Correct 888 ms 149136 KB Output is correct
29 Correct 1130 ms 153756 KB Output is correct
30 Correct 2183 ms 167740 KB Output is correct
31 Correct 288 ms 138232 KB Output is correct
32 Correct 1571 ms 156492 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 138364 KB Output is correct
2 Correct 297 ms 138488 KB Output is correct
3 Correct 288 ms 138388 KB Output is correct
4 Correct 301 ms 138340 KB Output is correct
5 Correct 307 ms 138532 KB Output is correct
6 Correct 291 ms 138360 KB Output is correct
7 Correct 261 ms 138104 KB Output is correct
8 Correct 265 ms 138100 KB Output is correct
9 Correct 261 ms 138136 KB Output is correct
10 Correct 263 ms 138104 KB Output is correct
11 Correct 289 ms 138488 KB Output is correct
12 Correct 292 ms 138488 KB Output is correct
13 Correct 303 ms 138616 KB Output is correct
14 Correct 310 ms 138740 KB Output is correct
15 Correct 300 ms 138104 KB Output is correct
16 Correct 268 ms 138104 KB Output is correct
17 Correct 259 ms 138192 KB Output is correct
18 Correct 2429 ms 169916 KB Output is correct
19 Correct 725 ms 143992 KB Output is correct
20 Correct 666 ms 142072 KB Output is correct
21 Correct 659 ms 142328 KB Output is correct
22 Correct 742 ms 143484 KB Output is correct
23 Correct 708 ms 144120 KB Output is correct
24 Correct 680 ms 142080 KB Output is correct
25 Correct 697 ms 142712 KB Output is correct
26 Correct 759 ms 143484 KB Output is correct
27 Correct 1146 ms 155660 KB Output is correct
28 Correct 888 ms 149136 KB Output is correct
29 Correct 1130 ms 153756 KB Output is correct
30 Correct 2183 ms 167740 KB Output is correct
31 Correct 288 ms 138232 KB Output is correct
32 Correct 1571 ms 156492 KB Output is correct
33 Correct 1557 ms 225412 KB Output is correct
34 Correct 1541 ms 274424 KB Output is correct
35 Correct 1698 ms 269620 KB Output is correct
36 Correct 1271 ms 231508 KB Output is correct
37 Correct 473 ms 144728 KB Output is correct
38 Correct 594 ms 150392 KB Output is correct
39 Execution timed out 3076 ms 225888 KB Time limit exceeded
40 Halted 0 ms 0 KB -