Submission #364936

#	Time	Username	Problem	Language	Result	Execution time	Memory
364936		kostia244	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	2428 ms	374796 KiB

rainbow

#include "rainbow.h"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int ans[1<<17];
struct seg {
	struct node {
		int sum = 0;
		node *l = 0, *r = 0;
	};
	node *rt;
	int n;
	seg(int N = 0) : rt(new node()), n(N) {}
	void update(node*& v, int l, int r, int p) {
		if(p < l || r < p) return;
		if(!v) v = new node();
		v->sum++;
		if(l == r) return;
		int mid = (l+r)/2;
		update(v->l, l, mid, p);
		update(v->r, mid+1, r, p);
	}
	int query(node *v, int l, int r, int ql, int qr) {
		if(!v || r < ql || qr < l) return 0;
		if(ql <= l && r <= qr) return v->sum;
		int mid = (l+r)/2;
		return query(v->l, l, mid, ql, qr) + query(v->r, mid+1, r, ql, qr);
	}
	void update(int p) { update(rt, 1, n, p); }
	int query(int ql, int qr) { return query(rt, 1, n, ql, qr); }
};
struct rect_query_online {
	vector<seg> st;
	int n;
	rect_query_online(int n = 0, int m = 0) : n(n), st(n+1) {
		for(int i = 1; i <= n; i++) st[i] = seg(m);
	}
	void add_point(int x, int y) {
		for(; x <= n; x += x&-x) st[x].update(y);
	}
	int query(int x, int yl, int yr) {
		int ans = 0;
		//cout << x << " " << yl << " " << yr << ": " << endl;
		for(; x; x -= x&-x) ans += st[x].query(yl, yr);
		//cout << ans << endl;
		return ans;
	}
	int query(int xl, int xr, int yl, int yr) {
		if(xl > xr || yl > yr) return 0;
		return query(xr, yl, yr) - query(xl-1, yl, yr);
	}
};
using pt = array<int, 2>;
int n, m;//segments are identified by their top left point
map<pt, int> points, segx, segy;
set<pt> marked;
void add_block(int x, int y) {
	if(!marked.insert({x, y}).second) return;
	points[{x, y}]++;
	points[{x+1, y}]++;
	points[{x, y+1}]++;
	points[{x+1, y+1}]++;
	segx[{x, y}]++;
	segx[{x, y+1}]++;
	segy[{x, y}]++;
	segy[{x+1, y}]++;
}
rect_query_online rp, rb, rx, ry;
int minx = 1<<30, miny = 1<<30, maxy = -1, maxx = -1;
void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R+1, m = C+1;
	add_block(sr, sc);
	minx = maxx = sr, miny = maxy = sc;
	for(int i = 0; i < M; i++) {
		if(S[i] == 'N') sr--;
		if(S[i] == 'S') sr++;
		if(S[i] == 'W') sc--;
		if(S[i] == 'E') sc++;
		add_block(sr, sc);
		minx = min(minx, sr);
		maxx = max(maxx, sr);
		miny = min(miny, sc);
		maxy = max(maxy, sc);
	}
	rp = rect_query_online(n, m);
	rx = rect_query_online(n, m);
	ry = rect_query_online(n, m);
	rb = rect_query_online(n, m);
	for(auto i : points) {
		rp.add_point(i.first[0], i.first[1]);
	}
	for(auto i : segx) {
		rx.add_point(i.first[0], i.first[1]);
	}
	for(auto i : segy) {
		ry.add_point(i.first[0], i.first[1]);
	}
	for(auto i : marked) {
		rb.add_point(i[0], i[1]);
	}
}
 
int colour(int xl, int yl, int xr, int yr) {
	xr++, yr++;
	//cout << xl << " " << xr << " " << yl << " " << yr << endl;
	int v, e, b;
	v = e = 2*(xr+yr-xl-yl);
	//cout << v << endl;
	v += rp.query(xl+1, xr-1, yl+1, yr-1);
	e += rx.query(xl, xr-1, yl+1, yr-1) + ry.query(xl+1, xr-1, yl, yr-1);
 	b = rb.query(xl, xr-1, yl, yr-1)+1;
    int f = e-v+2-b;
    f += xl < minx && maxx < xr-1 && yl < miny && maxy < yr-1;
    return f;
}

Compilation message (stderr)

rainbow.cpp: In constructor 'rect_query_online::rect_query_online(int, int)':
rainbow.cpp:37:6: warning: 'rect_query_online::n' will be initialized after [-Wreorder]
   37 |  int n;
      |      ^
rainbow.cpp:36:14: warning:   'std::vector<seg> rect_query_online::st' [-Wreorder]
   36 |  vector<seg> st;
      |              ^~
rainbow.cpp:38:2: warning:   when initialized here [-Wreorder]
   38 |  rect_query_online(int n = 0, int m = 0) : n(n), st(n+1) {
      |  ^~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26