oj.uz

Submission #251357

# Submission time Handle Problem Language Result Execution time Memory
251357 2020-07-21T01:29:13 Z Lawliet Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1116 ms 187568 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' };
 
int R, C;

class PersistentSegmentTree
{
	public:
 
		void copy(int node)
		{
			e.push_back( e[node] );
			d.push_back( d[node] );
			sum.push_back( sum[node] );
		}
 
		int update(int node, int l, int r, int i)
		{
			int newNode = ++cnt;
			copy( node );
 
			if( l == r )
			{
				sum[newNode]++;
				return newNode;
			}
 
			int m = ( l + r )/2;
 
			if( i <= m )
			{
				int aux = update( e[newNode] , l , m , i );
				e[newNode] = aux;
			}
			else
			{
				int aux = update( d[newNode] , m + 1 , r , i );
				d[newNode] = aux;
			}
 
			sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];

			return newNode;
		}

		void updateRoot() { root.push_back( root.back() ); }

		void update(int y)
		{
			if( y < 1 || C < y ) return;

			int r = update( root.back() , 1 , C , y );
			root.back() = r;
		}
 
		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;
		}

		int query(int x1, int y1, int x2, int y2)
		{
			int ans = query( root[x2] , 1 , C , y1 , y2 );
			ans -= query( root[x1 - 1] , 1 , C , y1 , y2 );

			return ans;
		}
 
		PersistentSegmentTree() : cnt(1)
		{
			e.resize( 2 , 0 ); d.resize( 2 , 0 );
			sum.resize( 2 , 0 ); root.resize( 1 , 1 );
		}
 
	protected:
 
		int cnt;
 
		vector<int> e, d;
		vector<int> sum, root;
};
 
int minY, maxY;
int minX, maxX;
 
PersistentSegmentTree faces;
PersistentSegmentTree vertices;
PersistentSegmentTree edgesVert, edgesHor;

vector<int> sweepFaces[MAXN];
vector<int> sweepVertices[MAXN];
vector<int> sweepEdgesVert[MAXN], sweepEdgesHor[MAXN];
 
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) 
{
	R = r; C = c;
	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 );
 
		sweepVertices[x].push_back( y );

		sweepEdgesHor[x].push_back( y );
		sweepEdgesVert[x].push_back( y );
 
		if( !inside( x - 1 , y ) )
			sweepEdgesVert[x - 1].push_back( y );
 
		if( !inside( x , y - 1 ) )
			sweepEdgesHor[x].push_back( y - 1 );
 
		sweepFaces[x].push_back( y );
 
		if( !inside( x - 1 , y ) )
			sweepFaces[x - 1].push_back( y );
 
		if( !inside( x , y - 1 ) && !inside( x + 1 , y - 1 ) )
			sweepFaces[x].push_back( y - 1 );
 
		if( !inside( x , y - 1 ) && !inside( x - 1 , y ) && !inside( x - 1 , y - 1 ) )
			sweepFaces[x - 1].push_back( y - 1 );
	}

	for(int i = 1 ; i <= R ; i++)
	{
		faces.updateRoot(); vertices.updateRoot();
		edgesHor.updateRoot(); edgesVert.updateRoot();

		while( !sweepFaces[i].empty() )
		{
			faces.update( sweepFaces[i].back() );
			sweepFaces[i].pop_back();
		}

		while( !sweepVertices[i].empty() )
		{
			vertices.update( sweepVertices[i].back() );
			sweepVertices[i].pop_back();
		}

		while( !sweepEdgesVert[i].empty() )
		{
			edgesVert.update( sweepEdgesVert[i].back() );
			sweepEdgesVert[i].pop_back();
		}

		while( !sweepEdgesHor[i].empty() )
		{
			edgesHor.update( sweepEdgesHor[i].back() );
			sweepEdgesHor[i].pop_back();
		}
	}
}
 
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:120: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 13 ms 19200 KB Output is correct
2 Correct 14 ms 19712 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 15 ms 19840 KB Output is correct
6 Correct 11 ms 19072 KB Output is correct
7 Correct 12 ms 18944 KB Output is correct
8 Correct 11 ms 19072 KB Output is correct
9 Correct 12 ms 19328 KB Output is correct
10 Correct 11 ms 19072 KB Output is correct
11 Correct 14 ms 19328 KB Output is correct
12 Correct 14 ms 19584 KB Output is correct
13 Correct 15 ms 20224 KB Output is correct
14 Correct 15 ms 20480 KB Output is correct
15 Correct 11 ms 19072 KB Output is correct
16 Correct 11 ms 19072 KB Output is correct
17 Correct 11 ms 19072 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 11 ms 19072 KB Output is correct
3 Correct 406 ms 104068 KB Output is correct
4 Correct 614 ms 147716 KB Output is correct
5 Correct 628 ms 144612 KB Output is correct
6 Correct 471 ms 111172 KB Output is correct
7 Correct 575 ms 106728 KB Output is correct
8 Correct 94 ms 19960 KB Output is correct
9 Correct 629 ms 146912 KB Output is correct
10 Correct 638 ms 144160 KB Output is correct
11 Correct 494 ms 110976 KB Output is correct
12 Correct 344 ms 146480 KB Output is correct
13 Correct 350 ms 147448 KB Output is correct
14 Correct 370 ms 144812 KB Output is correct
15 Correct 301 ms 111144 KB Output is correct
16 Correct 430 ms 117012 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 361 ms 179752 KB Output is correct
3 Correct 427 ms 186804 KB Output is correct
4 Correct 430 ms 167592 KB Output is correct
5 Correct 331 ms 139528 KB Output is correct
6 Correct 99 ms 52012 KB Output is correct
7 Correct 183 ms 77836 KB Output is correct
8 Correct 293 ms 114080 KB Output is correct
9 Correct 255 ms 102860 KB Output is correct
10 Correct 71 ms 40956 KB Output is correct
11 Correct 190 ms 97992 KB Output is correct
12 Correct 365 ms 179740 KB Output is correct
13 Correct 423 ms 186928 KB Output is correct
14 Correct 434 ms 167496 KB Output is correct
15 Correct 333 ms 139488 KB Output is correct
16 Correct 80 ms 43484 KB Output is correct
17 Correct 194 ms 77632 KB Output is correct
18 Correct 394 ms 164132 KB Output is correct
19 Correct 370 ms 146512 KB Output is correct
20 Correct 374 ms 146636 KB Output is correct
21 Correct 287 ms 113956 KB Output is correct
22 Correct 255 ms 102888 KB Output is correct
23 Correct 70 ms 40956 KB Output is correct
24 Correct 183 ms 97740 KB Output is correct
25 Correct 360 ms 179744 KB Output is correct
26 Correct 424 ms 186824 KB Output is correct
27 Correct 432 ms 167508 KB Output is correct
28 Correct 334 ms 139360 KB Output is correct
29 Correct 79 ms 43500 KB Output is correct
30 Correct 186 ms 77588 KB Output is correct
31 Correct 405 ms 164312 KB Output is correct
32 Correct 382 ms 146488 KB Output is correct
33 Correct 389 ms 146564 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 14 ms 19712 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 15 ms 19840 KB Output is correct
6 Correct 11 ms 19072 KB Output is correct
7 Correct 12 ms 18944 KB Output is correct
8 Correct 11 ms 19072 KB Output is correct
9 Correct 12 ms 19328 KB Output is correct
10 Correct 11 ms 19072 KB Output is correct
11 Correct 14 ms 19328 KB Output is correct
12 Correct 14 ms 19584 KB Output is correct
13 Correct 15 ms 20224 KB Output is correct
14 Correct 15 ms 20480 KB Output is correct
15 Correct 11 ms 19072 KB Output is correct
16 Correct 11 ms 19072 KB Output is correct
17 Correct 11 ms 19072 KB Output is correct
18 Correct 749 ms 65192 KB Output is correct
19 Correct 230 ms 22120 KB Output is correct
20 Correct 167 ms 20216 KB Output is correct
21 Correct 193 ms 20600 KB Output is correct
22 Correct 203 ms 21240 KB Output is correct
23 Correct 232 ms 22120 KB Output is correct
24 Correct 163 ms 20472 KB Output is correct
25 Correct 189 ms 20984 KB Output is correct
26 Correct 204 ms 21496 KB Output is correct
27 Correct 279 ms 55580 KB Output is correct
28 Correct 208 ms 37060 KB Output is correct
29 Correct 276 ms 52840 KB Output is correct
30 Correct 541 ms 109972 KB Output is correct
31 Correct 14 ms 19200 KB Output is correct
32 Correct 510 ms 56080 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 14 ms 19712 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 15 ms 19840 KB Output is correct
6 Correct 11 ms 19072 KB Output is correct
7 Correct 12 ms 18944 KB Output is correct
8 Correct 11 ms 19072 KB Output is correct
9 Correct 12 ms 19328 KB Output is correct
10 Correct 11 ms 19072 KB Output is correct
11 Correct 14 ms 19328 KB Output is correct
12 Correct 14 ms 19584 KB Output is correct
13 Correct 15 ms 20224 KB Output is correct
14 Correct 15 ms 20480 KB Output is correct
15 Correct 11 ms 19072 KB Output is correct
16 Correct 11 ms 19072 KB Output is correct
17 Correct 11 ms 19072 KB Output is correct
18 Correct 749 ms 65192 KB Output is correct
19 Correct 230 ms 22120 KB Output is correct
20 Correct 167 ms 20216 KB Output is correct
21 Correct 193 ms 20600 KB Output is correct
22 Correct 203 ms 21240 KB Output is correct
23 Correct 232 ms 22120 KB Output is correct
24 Correct 163 ms 20472 KB Output is correct
25 Correct 189 ms 20984 KB Output is correct
26 Correct 204 ms 21496 KB Output is correct
27 Correct 279 ms 55580 KB Output is correct
28 Correct 208 ms 37060 KB Output is correct
29 Correct 276 ms 52840 KB Output is correct
30 Correct 541 ms 109972 KB Output is correct
31 Correct 14 ms 19200 KB Output is correct
32 Correct 510 ms 56080 KB Output is correct
33 Correct 361 ms 179752 KB Output is correct
34 Correct 427 ms 186804 KB Output is correct
35 Correct 430 ms 167592 KB Output is correct
36 Correct 331 ms 139528 KB Output is correct
37 Correct 99 ms 52012 KB Output is correct
38 Correct 183 ms 77836 KB Output is correct
39 Correct 293 ms 114080 KB Output is correct
40 Correct 255 ms 102860 KB Output is correct
41 Correct 71 ms 40956 KB Output is correct
42 Correct 190 ms 97992 KB Output is correct
43 Correct 365 ms 179740 KB Output is correct
44 Correct 423 ms 186928 KB Output is correct
45 Correct 434 ms 167496 KB Output is correct
46 Correct 333 ms 139488 KB Output is correct
47 Correct 80 ms 43484 KB Output is correct
48 Correct 194 ms 77632 KB Output is correct
49 Correct 394 ms 164132 KB Output is correct
50 Correct 370 ms 146512 KB Output is correct
51 Correct 374 ms 146636 KB Output is correct
52 Correct 287 ms 113956 KB Output is correct
53 Correct 255 ms 102888 KB Output is correct
54 Correct 70 ms 40956 KB Output is correct
55 Correct 183 ms 97740 KB Output is correct
56 Correct 360 ms 179744 KB Output is correct
57 Correct 424 ms 186824 KB Output is correct
58 Correct 432 ms 167508 KB Output is correct
59 Correct 334 ms 139360 KB Output is correct
60 Correct 79 ms 43500 KB Output is correct
61 Correct 186 ms 77588 KB Output is correct
62 Correct 405 ms 164312 KB Output is correct
63 Correct 382 ms 146488 KB Output is correct
64 Correct 389 ms 146564 KB Output is correct
65 Correct 1070 ms 114516 KB Output is correct
66 Correct 1116 ms 103628 KB Output is correct
67 Correct 412 ms 41592 KB Output is correct
68 Correct 453 ms 97740 KB Output is correct
69 Correct 705 ms 179744 KB Output is correct
70 Correct 559 ms 187568 KB Output is correct
71 Correct 645 ms 168412 KB Output is correct
72 Correct 497 ms 139236 KB Output is correct
73 Correct 168 ms 44252 KB Output is correct
74 Correct 306 ms 78312 KB Output is correct
75 Correct 486 ms 164760 KB Output is correct
76 Correct 693 ms 147248 KB Output is correct
77 Correct 643 ms 147204 KB Output is correct
78 Correct 406 ms 104068 KB Output is correct
79 Correct 614 ms 147716 KB Output is correct
80 Correct 628 ms 144612 KB Output is correct
81 Correct 471 ms 111172 KB Output is correct
82 Correct 575 ms 106728 KB Output is correct
83 Correct 94 ms 19960 KB Output is correct
84 Correct 629 ms 146912 KB Output is correct
85 Correct 638 ms 144160 KB Output is correct
86 Correct 494 ms 110976 KB Output is correct
87 Correct 344 ms 146480 KB Output is correct
88 Correct 350 ms 147448 KB Output is correct
89 Correct 370 ms 144812 KB Output is correct
90 Correct 301 ms 111144 KB Output is correct
91 Correct 430 ms 117012 KB Output is correct