oj.uz

Submission #409188

# Submission time Handle Problem Language Result Execution time Memory
409188 2021-05-20T10:38:37 Z cheissmart Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 102 ms 9500 KB 
#ifndef CHEISSMART
#include "rainbow.h"
#endif
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 2e5 + 7;

int di[] = {1, -1, 0, 0}, dj[] = {0, 0, 1, -1};

V<pi> bad;
int R, C;
int a[2][N], nw[3][N], nwp[3][N];

void init(int R, int C, int sr, int sc, int M, char *S) {
	::R = R, ::C = C;
	bad.EB(sr - 1, sc - 1);
	for(int i = 0; i < M; i++) {
		if(S[i] == 'N') sr--;
		else if(S[i] == 'S') sr++;
		else if(S[i] == 'W') sc--;
		else sc++;
		bad.EB(sr - 1, sc - 1);
	}
	sort(ALL(bad));
	bad.resize(unique(ALL(bad)) - bad.begin());
	for(pi p:bad) a[p.F][p.S] = 1;
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < N; j++) {
			if(a[i][j] == 0 && (j == 0 || a[i][j - 1] == 1)) 
				nw[i][j] = 1;
			nwp[i][j] = nw[i][j] + (j ? nwp[i][j - 1] : 0);
		}
	}
	for(int j = 0; j < N; j++) {
		if(a[0][j] == 0 || a[1][j] == 0) {
			nw[2][j] = 1;
			if(j && a[0][j] ==0 && a[0][j - 1] == 0)
				nw[2][j] = 0;
			if(j && a[1][j] ==0 && a[1][j - 1] == 0)
				nw[2][j] = 0;
		}
		nwp[2][j] = nw[2][j] + (j ? nwp[2][j - 1] : 0);
	}
}

int colour(int ar, int ac, int br, int bc) {
	ar--, ac--, br--, bc--;
	if(bc == ac) {
		return a[ar][ac] == 0 || a[br][ac] == 0;
	}
	int res = 0;
	if(ar == br) {
		res += nwp[ar][bc] - nwp[ar][ac];
		if(a[ar][ac] == 0 && nw[ar][ac + 1] == 0)
			res++;
	} else {
		res += nwp[2][bc] - nwp[2][ac];
		if(a[ar][ac] == 0 || a[br][ac] == 0)
			if(nw[2][ac + 1] == 0)
				res++;
	}
	return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Correct 4 ms 3404 KB Output is correct
3 Correct 72 ms 7644 KB Output is correct
4 Correct 75 ms 9500 KB Output is correct
5 Correct 96 ms 9444 KB Output is correct
6 Correct 102 ms 8776 KB Output is correct
7 Correct 72 ms 8756 KB Output is correct
8 Correct 71 ms 8008 KB Output is correct
9 Correct 82 ms 9460 KB Output is correct
10 Correct 85 ms 9356 KB Output is correct
11 Correct 77 ms 8788 KB Output is correct
12 Correct 66 ms 8276 KB Output is correct
13 Correct 66 ms 9396 KB Output is correct
14 Correct 66 ms 9384 KB Output is correct
15 Correct 68 ms 8652 KB Output is correct
16 Correct 75 ms 7992 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Runtime error 9 ms 2496 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -