oj.uz

Submission #625105

# Submission time Handle Problem Language Result Execution time Memory
625105 2022-08-09T11:15:28 Z QwertyPi Land of the Rainbow Gold (APIO17_rainbow) C++14
38 / 100
 335 ms 87128 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 13;

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

int dir[256];
int bx1 = INT32_MAX, bx2 = INT32_MIN, by1 = INT32_MAX, by2 = INT32_MIN;

struct DS{
	int bit[1002][1002] = {0};
	unordered_set<ll> S;
	string name;
	DS(string _n) : name(_n){}
	void add(int x, int y){
		x++; y++;
		// cout << name << "-ADD: " << x << ' ' << y << endl; 
		if(S.count(x * N + y))
			return;
		S.insert(x * N + y);
		for(int i = x; i <= 1001; i += i & -i){
			for(int j = y; j <= 1001; j += j & -j){
				bit[i][j] += 1;
			}
		}
	}
	int qry(int x, int y){
		x++; y++;
		// cout << name << "-QRY: " << x << ' ' << y << endl;
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			for(int j = y; j; j -= j & -j){
				ret += bit[i][j];
			}
		}
		return ret;
	}
	int qry(int x1, int x2, int y1, int y2){
		return qry(x2, y2) + qry(x1 - 1, y1 - 1) - qry(x2, y1 - 1) - qry(x1 - 1, y2);
	}
} V("V"), E1("E1"), E2("E2"), SQ("SQ");

void upd(int x, int y){
	bx1 = min(bx1, x);
	bx2 = max(bx2, x);
	by1 = min(by1, y);
	by2 = max(by2, y);
	
	V.add(x, y);
	E1.add(x, y - 1);
	E1.add(x, y);
	E2.add(x - 1, y);
	E2.add(x, y);
	SQ.add(x - 1, y - 1);
	SQ.add(x - 1, y);
	SQ.add(x, y - 1);
	SQ.add(x, y);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	dir['E'] = 0;
	dir['W'] = 1;
	dir['S'] = 2;
	dir['N'] = 3;
	upd(sr, sc);
	for(int i = 0; i < M; i++){
		sr += dx[dir[S[i]]];
		sc += dy[dir[S[i]]];
		upd(sr, sc);
	}
}

int colour(int ar, int ac, int br, int bc) {
	int x1 = ar, x2 = br, y1 = ac, y2 = bc;
	int v 	= (x2 - x1 + 1) * (y2 - y1 + 1) - V.qry(x1, x2, y1, y2);
	int e1 	= (x2 - x1 + 1) * (y2 - y1) - E1.qry(x1, x2, y1, y2 - 1);
	int e2  = (x2 - x1) * (y2 - y1 + 1) - E2.qry(x1, x2 - 1, y1, y2);
	int sq  = (x2 - x1) * (y2 - y1) - SQ.qry(x1, x2 - 1, y1, y2 - 1);
    return v - e1 - e2 + sq + (x1 < bx1 && bx2 < x2 && y1 < by1 && by2 < y2);
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:71:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   71 |   sr += dx[dir[S[i]]];
      |                ~~~^
rainbow.cpp:72:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   72 |   sc += dy[dir[S[i]]];
      |                ~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 16228 KB Output is correct
3 Correct 8 ms 16076 KB Output is correct
4 Correct 8 ms 16044 KB Output is correct
5 Correct 8 ms 16208 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 8 ms 15908 KB Output is correct
9 Correct 7 ms 15912 KB Output is correct
10 Correct 7 ms 15960 KB Output is correct
11 Correct 8 ms 16052 KB Output is correct
12 Correct 8 ms 16084 KB Output is correct
13 Correct 8 ms 16340 KB Output is correct
14 Correct 9 ms 16468 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Incorrect 133 ms 34532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Runtime error 117 ms 87128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 16228 KB Output is correct
3 Correct 8 ms 16076 KB Output is correct
4 Correct 8 ms 16044 KB Output is correct
5 Correct 8 ms 16208 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 8 ms 15908 KB Output is correct
9 Correct 7 ms 15912 KB Output is correct
10 Correct 7 ms 15960 KB Output is correct
11 Correct 8 ms 16052 KB Output is correct
12 Correct 8 ms 16084 KB Output is correct
13 Correct 8 ms 16340 KB Output is correct
14 Correct 9 ms 16468 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 312 ms 32636 KB Output is correct
19 Correct 106 ms 20008 KB Output is correct
20 Correct 88 ms 19480 KB Output is correct
21 Correct 97 ms 19640 KB Output is correct
22 Correct 116 ms 19664 KB Output is correct
23 Correct 100 ms 20008 KB Output is correct
24 Correct 87 ms 19532 KB Output is correct
25 Correct 98 ms 19724 KB Output is correct
26 Correct 106 ms 19836 KB Output is correct
27 Correct 257 ms 29888 KB Output is correct
28 Correct 231 ms 24660 KB Output is correct
29 Correct 247 ms 29312 KB Output is correct
30 Correct 335 ms 45308 KB Output is correct
31 Correct 8 ms 16060 KB Output is correct
32 Correct 169 ms 30088 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 16228 KB Output is correct
3 Correct 8 ms 16076 KB Output is correct
4 Correct 8 ms 16044 KB Output is correct
5 Correct 8 ms 16208 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 8 ms 15908 KB Output is correct
9 Correct 7 ms 15912 KB Output is correct
10 Correct 7 ms 15960 KB Output is correct
11 Correct 8 ms 16052 KB Output is correct
12 Correct 8 ms 16084 KB Output is correct
13 Correct 8 ms 16340 KB Output is correct
14 Correct 9 ms 16468 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 312 ms 32636 KB Output is correct
19 Correct 106 ms 20008 KB Output is correct
20 Correct 88 ms 19480 KB Output is correct
21 Correct 97 ms 19640 KB Output is correct
22 Correct 116 ms 19664 KB Output is correct
23 Correct 100 ms 20008 KB Output is correct
24 Correct 87 ms 19532 KB Output is correct
25 Correct 98 ms 19724 KB Output is correct
26 Correct 106 ms 19836 KB Output is correct
27 Correct 257 ms 29888 KB Output is correct
28 Correct 231 ms 24660 KB Output is correct
29 Correct 247 ms 29312 KB Output is correct
30 Correct 335 ms 45308 KB Output is correct
31 Correct 8 ms 16060 KB Output is correct
32 Correct 169 ms 30088 KB Output is correct
33 Runtime error 117 ms 87128 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -