oj.uz

Submission #466271

# Submission time Handle Problem Language Result Execution time Memory
466271 2021-08-18T12:42:51 Z Namnamseo Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 196 ms 156328 KB 
#include "rainbow.h"
#include <algorithm>
#include <vector>
#include <tuple>
#define x first
#define y second
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define sort_and_unique(v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }
using namespace std;
using pp=pair<int,int>;
using ll=long long;

const int maxm = int(1e5) + 10;

vector<pp> riv, eh, ev, e4;
void River(int sx, int sy, int m, char *s) {
	riv.resize(m+1);
	for (int i=0; i<m; ++i) {
		riv[i] = {sx, sy};
		if (s[i] == 'S') ++sx; else if (s[i] == 'N') --sx;
		else if (s[i] == 'E') ++sy; else --sy;
	}
	riv[m++] = {sx, sy};
	sort_and_unique(riv); m = riv.size();
	eh = riv; ev = riv; eh.resize(2*m); ev.resize(2*m);
	for (int i=0, x, y; i<m; ++i) { tie(x, y) = riv[i];
		eh[m+i] = {x, y-1}; ev[m+i] = {x-1, y};
	}
	sort_and_unique(eh); sort_and_unique(ev);
	e4 = riv; e4.resize(4*m);
	for (int i=0, j=m, x, y; i<m; ++i) { tie(x, y) = riv[i];
		e4[j++] = {x-1, y};
		e4[j++] = {x, y-1};
		e4[j++] = {x-1, y-1};
	}
	sort_and_unique(e4);
}

struct MST {
	const static int M = 262144;
	vector<int> t[M<<1];
	void put(int x, int y) { t[M+x].pb(y); }
	void init() {
		for (int i=M-1; 1<=i; --i) {
			static int tmp[maxm];
			int s = merge(all(t[i*2]), all(t[i*2+1]), tmp) - tmp;
			t[i] = vector<int>(tmp, tmp+s);
		}
	}
	int rq(int l, int r, int d, int u) { if (d>u) return 0;
		int x = 0;
		auto vq = [&](const vector<int> &v) -> int {
			return upper_bound(all(v), u) - lower_bound(all(v), d);
		};
		for (l+=M, r+=M; l<=r; l/=2, r/=2) {
			if (l%2 == 1) x += vq(t[l++]);
			if (r%2 == 0) x += vq(t[r--]);
		}
		return x;
	}
} triv, teh, tev, te4;

void Write() {
#define wr(v, t) for (auto &tmp:v) t.put(tmp.x, tmp.y); t.init();
	wr(riv, triv);
	wr(eh, teh);
	wr(ev, tev);
	wr(e4, te4);
#undef wr
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	River(sr, sc, M, S);
	Write();
}

int colour(int ar, int ac, int br, int bc) {
	ll w = br-ar+1, h = bc-ac+1;
	ll inv = w * h;
	ll ine = (w-1)*h + w*(h-1);
	ll inf = (w-1)*(h-1);

	inv -= triv.rq(ar, br, ac, bc);
	ine -= teh.rq(ar, br, ac, bc-1);
	ine -= tev.rq(ar, br-1, ac, bc);
	inf -= te4.rq(ar, br-1, ac, bc-1);
    return inv - ine + inf;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 49688 KB Output is correct
2 Correct 37 ms 49972 KB Output is correct
3 Incorrect 35 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49420 KB Output is correct
2 Correct 34 ms 49516 KB Output is correct
3 Correct 185 ms 81784 KB Output is correct
4 Runtime error 179 ms 148820 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49484 KB Output is correct
2 Runtime error 196 ms 156328 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 49688 KB Output is correct
2 Correct 37 ms 49972 KB Output is correct
3 Incorrect 35 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 49688 KB Output is correct
2 Correct 37 ms 49972 KB Output is correct
3 Incorrect 35 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -