oj.uz

Submission #97231

# Submission time Handle Problem Language Result Execution time Memory
97231 2019-02-14T14:23:23 Z E869120 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 3000 ms 205168 KB 
#include "rainbow.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const long long BASE = 1LL;

vector<bool> used[2009]; int H, W, minx = (1 << 30), miny = (1 << 30), maxx = 0, maxy = 0;
vector<int> A[4][2009], A2[2009], A3[2009], A4[2009];
vector<pair<int, int>> G[4];

map<int, int> M[4][200009];

void add(int ty, int px, int py, int r) {
	int X = px, Y = py;
	while (X <= H) {
		Y = py;
		while (Y <= W) {
			M[ty][X][Y] += r;
			Y += (Y&-Y);
		}
		X += (X&-X);
	}
}
int sum(int ty, int px, int py) {
	int s = 0, X = px, Y = py;
	while (X >= 1) {
		Y = py;
		while (Y >= 1) {
			s += M[ty][X][Y];
			Y -= (Y&-Y);
		}
		X -= (X&-X);
	}
	return s;
}

void putvector(int px, int py) {
	G[0].push_back(make_pair(px, py));
	G[1].push_back(make_pair(px, py - 1));
	G[1].push_back(make_pair(px, py));
	G[2].push_back(make_pair(px - 1, py));
	G[2].push_back(make_pair(px, py));
	G[3].push_back(make_pair(px - 1, py - 1));
	G[3].push_back(make_pair(px - 1, py));
	G[3].push_back(make_pair(px, py - 1));
	G[3].push_back(make_pair(px, py));
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	H = R; W = C;
	if (1LL * H*W <= BASE) {
		for (int i = 0; i <= H; i++) used[i].resize(W + 1, true);
		for (int i = 0; i <= H; i++) { for (int j = 0; j < 4; j++) A[j][i].resize(W + 1, 0); }

		int cx = sr, cy = sc; used[cx][cy] = false; minx = cx; miny = cy; maxx = cx; maxy = cy;
		for (int i = 0; i < M; i++) {
			if (S[i] == 'E') cy++;
			if (S[i] == 'W') cy--;
			if (S[i] == 'N') cx--;
			if (S[i] == 'S') cx++;
			used[cx][cy] = false;
			minx = min(minx, cx); maxx = max(maxx, cx);
			miny = min(miny, cy); maxy = max(maxy, cy);
		}
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) { if (used[i][j] == true) A[0][i][j] = 1; }
		}
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W - 1; j++) { if (used[i][j] == true && used[i][j + 1] == true) A[1][i][j] = 1; }
		}
		for (int i = 1; i <= H - 1; i++) {
			for (int j = 1; j <= W; j++) { if (used[i][j] == true && used[i + 1][j] == true) A[2][i][j] = 1; }
		}
		for (int i = 1; i <= H - 1; i++) {
			for (int j = 1; j <= W - 1; j++) { if (used[i][j] == true && used[i][j + 1] == true && used[i + 1][j] == true && used[i + 1][j + 1] == true) A[3][i][j] = 1; }
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j <= H; j++) {
				for (int k = 1; k <= W; k++) A[i][j][k] += A[i][j][k - 1];
			}
			for (int j = 1; j <= H; j++) {
				for (int k = 0; k <= W; k++) A[i][j][k] += A[i][j - 1][k];
			}
		}
	}
	else {
		int cx = sr, cy = sc; putvector(cx, cy);
		for (int i = 0; i < M; i++) {
			if (S[i] == 'E') cy++;
			if (S[i] == 'W') cy--;
			if (S[i] == 'N') cx--;
			if (S[i] == 'S') cx++;
			putvector(cx, cy);
			minx = min(minx, cx); maxx = max(maxx, cx);
			miny = min(miny, cy); maxy = max(maxy, cy);
		}
		for (int i = 0; i < 4; i++) {
			sort(G[i].begin(), G[i].end());
			G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < G[i].size(); j++) {
				if (G[i][j].first == 0 || G[i][j].second == 0) continue;
				add(i, G[i][j].first, G[i][j].second, 1);
			}
		}
	}
}

int ranged(int ty, int px, int py, int qx, int qy) {
	if (px > qx || py > qy) return 0;
	return A[ty][px - 1][py - 1] + A[ty][qx][qy] - A[ty][px - 1][qy] - A[ty][qx][py - 1];
}
long long big_ranged_attack(int ty, int px, int py, int qx, int qy) {
	if (px > qx || py > py) return 0;

	int V1 = sum(ty, px - 1, py - 1);
	int V2 = sum(ty, px - 1, qy);
	int V3 = sum(ty, qx, py - 1);
	int V4 = sum(ty, qx, qy);
	return V1 - V2 - V3 + V4;
	/*int rem = 0;
	for (int i = 0; i < G[ty].size(); i++) {
		if (px <= G[ty][i].first && G[ty][i].first <= qx && py <= G[ty][i].second && G[ty][i].second <= qy) rem++;
	}
	return rem;*/
}

int colour(int ar, int ac, int br, int bc) {
	if (1LL * H*W <= BASE) {
		int Z1 = ranged(0, ar, ac, br, bc);
		int Z2 = ranged(1, ar, ac, br, bc - 1);
		int Z3 = ranged(2, ar, ac, br - 1, bc);
		int Z4 = ranged(3, ar, ac, br - 1, bc - 1);
		int BONUS = 0; if (ar < minx && maxx < br && ac < miny && maxy < bc) BONUS = 1;
		return (Z1 - Z2 - Z3 + Z4 + BONUS);
	}
	else {
		long long V1 = br - ar + 1, V2 = bc - ac + 1;
		long long Z1 = V1 * V2 - big_ranged_attack(0, ar, ac, br, bc);
		long long Z2 = V1 * (V2 - 1) - big_ranged_attack(1, ar, ac, br, bc - 1);
		long long Z3 = (V1 - 1) * V2 - big_ranged_attack(2, ar, ac, br - 1, bc);
		long long Z4 = (V1 - 1) * (V2 - 1) - big_ranged_attack(3, ar, ac, br - 1, bc - 1);
		long long BONUS = 0; if (ar < minx && maxx < br && ac < miny && maxy < bc) BONUS = 1;
		return (Z1 - Z2 - Z3 + Z4 + BONUS);
	}
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
rainbow.cpp: In function 'long long int big_ranged_attack(int, int, int, int, int)':
rainbow.cpp:118:20: warning: self-comparison always evaluates to false [-Wtautological-compare]
  if (px > qx || py > py) return 0;
                 ~~~^~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38396 KB Output is correct
2 Correct 50 ms 38904 KB Output is correct
3 Correct 52 ms 38776 KB Output is correct
4 Correct 48 ms 38776 KB Output is correct
5 Correct 46 ms 38904 KB Output is correct
6 Correct 37 ms 38264 KB Output is correct
7 Incorrect 35 ms 38264 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 38364 KB Output is correct
2 Incorrect 38 ms 38236 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 38264 KB Output is correct
2 Execution timed out 3079 ms 205168 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38396 KB Output is correct
2 Correct 50 ms 38904 KB Output is correct
3 Correct 52 ms 38776 KB Output is correct
4 Correct 48 ms 38776 KB Output is correct
5 Correct 46 ms 38904 KB Output is correct
6 Correct 37 ms 38264 KB Output is correct
7 Incorrect 35 ms 38264 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38396 KB Output is correct
2 Correct 50 ms 38904 KB Output is correct
3 Correct 52 ms 38776 KB Output is correct
4 Correct 48 ms 38776 KB Output is correct
5 Correct 46 ms 38904 KB Output is correct
6 Correct 37 ms 38264 KB Output is correct
7 Incorrect 35 ms 38264 KB Output isn't correct
8 Halted 0 ms 0 KB -