Submission #625105

#	Time	Username	Problem	Language	Result	Execution time	Memory
625105		QwertyPi	Land of the Rainbow Gold (APIO17_rainbow)	C++14	38 / 100	335 ms	87128 KiB

rainbow

#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 (stderr)

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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 27 / 27
• Subtask 5: 0 / 26