oj.uz

Submission #251352

# Submission time Handle Problem Language Result Execution time Memory
251352 2020-07-21T00:20:39 Z Lawliet Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 289592 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];
};

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) 
{
	int n = strlen( S );

	river.insert( { sr , sc } );

	for(int i = 0 ; i < n ; i++)
	{
		int d = conv( S[i] );
		sr += dx[d]; sc += dy[d];

		river.insert( { sr , sc } );
	}

	for(auto it = river.begin() ; it != river.end() ; it++)
	{
		int x = it->first;
		int y = it->second;

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

    return qtdVertices - qtdEdges + qtdFaces;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 138232 KB Output is correct
2 Correct 311 ms 138744 KB Output is correct
3 Incorrect 280 ms 138360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 138104 KB Output is correct
2 Correct 257 ms 138104 KB Output is correct
3 Correct 2430 ms 247680 KB Output is correct
4 Execution timed out 3093 ms 289592 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 138244 KB Output is correct
2 Correct 1568 ms 225500 KB Output is correct
3 Correct 1477 ms 274560 KB Output is correct
4 Correct 1621 ms 269796 KB Output is correct
5 Correct 1253 ms 231732 KB Output is correct
6 Correct 461 ms 145016 KB Output is correct
7 Incorrect 595 ms 150776 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 138232 KB Output is correct
2 Correct 311 ms 138744 KB Output is correct
3 Incorrect 280 ms 138360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 138232 KB Output is correct
2 Correct 311 ms 138744 KB Output is correct
3 Incorrect 280 ms 138360 KB Output isn't correct
4 Halted 0 ms 0 KB -