제출 #959721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959721		beaboss	무지개나라 (APIO17_rainbow)	C++17	0 / 100	62 ms	103764 KiB

rainbow

// Source: https://dmoj.ca/problem/apio17p1
// 
#include "rainbow.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 5e5 + 10;
int cnt = 1;

int seg[100 * N], rightc[100 * N], leftc[100 * N];

struct Segtree {
	set<int> need[N];
	int roots[N];

	void add(int x, int y) {
		need[x].insert(y);
	}

	void build() {
		roots[0]=0;
		FOR(i, 1, N) {
			roots[i]=roots[i-1];
			for (auto val: need[i]) update(val, roots[i]);
		}
	}

	void update(int pos, int &node, int l = 0, int r = N) {
		if (r <= l) return;
		if (pos < l || pos >= r) return;
		// cout << l << r << endl;
		seg[cnt] = seg[node] + 1; // update
		leftc[cnt] = leftc[node];
		rightc[cnt] = rightc[node];
		node=cnt;
		cnt++;
		if (l == r-1) return;

		int m = (l + r) / 2;
		if (pos < m) update(pos, leftc[node], l, m);
		if (pos >= m) update(pos, rightc[node], m, r);
	}

	int query(int node, int ql, int qr, int l, int r) {
		if (r <= l) return 0;
		if (node == 0) return 0;
		if (l == r) return 0;

		if (ql <= l && r <= qr) return seg[node];
		int acc = 0;

		int m = (l + r) / 2;
		if (ql < m) acc += query(leftc[node], ql, qr, l, m);
		if (qr > m) acc += query(rightc[node], ql, qr, m, r);

		return acc;

	}

	int query(int x1, int y1, int x2, int y2) { // inclusive exclusive
		return query(roots[x2-1], y1, y2, 0, N) - query(roots[x1-1], y1, y2, 0, N);
	}
} river, edgeh, edgev, vert;

void add(int x, int y) {
	// cout << x << y << endl;
	river.add(x, y);
	edgeh.add(x, y);
	edgeh.add(x+1, y);
	edgev.add(x, y);
	edgev.add(x, y+1);
	vert.add(x, y);
	vert.add(x+1, y);
	vert.add(x, y+1);
	vert.add(x+1, y+1);

}

int mnx = N, mny = N;
int mxx = 0, mxy = 0;

void init(int r, int c, int sr, int sc, int m, char* str) {
	r = sr;
	c = sc;
	add(r, c);


	FOR(i, 0, m) {
		if (str[i] == 'N') r--;
		if (str[i] == 'E') c++;
		if (str[i] == 'W') c--;
		if (str[i] == 'S') r++;
		add(r, c);
		ckmin(mnx, r);
		ckmax(mxx, r);
		ckmin(mny, c);
		ckmax(mxy, c);
	}

	river.build();
	edgeh.build();
	edgev.build();
	vert.build();

}

int colour(int ar, int ac, int br, int bc) {
	int e = edgeh.query(ar+1, ac, br+1, bc+1) + edgev.query(ar, ac+1, br+1, bc+1);
	int r = river.query(ar, ac, br+1, bc+1);
	int v = vert.query(ar+1, ac+1, br+1, bc+1);
	int c = (ar >= mnx || br <= mxx || ac >= mny || bc <= mxy ? 1 : 2);
	// cout << e << ' ' << v << ' ' << c << ' ' << r << endl;
	return e-v+c-r;
}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);


// 	init(6, 4, 3, 3, 9, "NWESSWEWS");
// 	// FOR(x, 1, 10) {
// 	// 	FOR(y, 1, 10) cout << river.query(river.roots[x], y, y+1, 0, N) - river.query(river.roots[x-1], y, y+1, 0, N) << ' ';
// 	// 	cout << endl;
// 	// }
// 	// cout << seg[0] << endl;
// 	int a, b, c, d;
// 	while (true) {
// 		cin >> a >> b >> c >> d;
// 		cout << colour(a, b, c, d) << endl;
// 	}
	
// }

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