Submission #1271477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271477		kaiboy	영역 (JOI16_ho_t4)	C++20	100 / 100	30 ms	9032 KiB

2016_ho_t4

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100000;

char cc[N + 1];
long long xx[N], yy[N];
long long xxo[N], yyo[N], ll[N], rr[N], ii[N];
long long xxo_[N], yyo_[N], ll_[N], rr_[N];
long long aa[N * 8];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, k; cin >> n >> k >> cc;
	long long x_ = 0, y_ = 0;
	for (int i = 0; i < n; i++) {
		xx[i] = x_;
		yy[i] = y_;
		char c = cc[i];
		if (c == 'E')
			x_++;
		else if (c == 'N')
			y_++;
		else if (c == 'W')
			x_--;
		else
			y_--;
	}
	if (x_ < 0) {
		for (int i = 0; i < n; i++)
			xx[i] *= -1;
		x_ *= -1;
	}
	if (y_ < 0) {
		for (int i = 0; i < n; i++)
			yy[i] *= -1;
		y_ *= -1;
	}
	if (!x_) {
		for (int i = 0; i < n; i++)
			swap(xx[i], yy[i]);
		swap(x_, y_);
	}
	if (!x_)
		k = 1;
	for (int i = 0; i < n; i++) {
		long long xo = xx[i], yo = yy[i], a = 0;
		if (x_)
			if (xo < 0) {
				long long b = (-xo + x_ - 1) / x_;
				xo += x_ * b;
				yo += y_ * b;
				a -= b;
			} else {
				long long b = xo / x_;
				xo -= x_ * b;
				yo -= y_ * b;
				a += b;
			}
		xxo[i] = xo;
		yyo[i] = yo;
		ll[i] = a;
		rr[i] = a + k;
		if (!i)
			rr[i]++;
		ii[i] = i;
	}
	sort(ii, ii + n, [] (int i, int j) {
			if (xxo[i] != xxo[j])
			return xxo[i] < xxo[j];
			if (yyo[i] != yyo[j])
			return yyo[i] < yyo[j];
			return ll[i] < ll[j];
			});
	int n_ = 0;
	for (int hl = 0, hr; hl < n; hl = hr) {
		int i = ii[hl];
		long long xo = xxo[i], yo = yyo[i], l = ll[i], r = rr[i];
		for (hr = hl + 1; hr < n; hr++) {
			i = ii[hr];
			if (xxo[i] > xo || yyo[i] > yo)
				break;
			if (ll[i] <= r)
				r = max(r, rr[i]);
			else {
				xxo_[n_] = xo;
				yyo_[n_] = yo;
				ll_[n_] = l;
				rr_[n_] = r;
				n_++;
				l = ll[i];
				r = rr[i];
			}
		}
		xxo_[n_] = xo;
		yyo_[n_] = yo;
		ll_[n_] = l;
		rr_[n_] = r;
		n_++;
	}
	n = n_;
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		xxo[i] = xxo_[i];
		yyo[i] = yyo_[i];
		ll[i] = ll_[i];
		rr[i] = rr_[i];
	}
	for (int i0 = 0; i0 < n; i0++) {
		long long xo0 = xxo[i0], yo0 = yyo[i0];
		if (i0 && xo0 == xxo[i0 - 1] && yo0 == yyo[i0 - 1])
			continue;
		long long xo1 = xo0, yo1 = yo0 + 1;
		long long xo2 = xo0 + 1, yo2 = yo0;
		long long xo3 = xo0 + 1, yo3 = yo0 + 1;
		if (x_ && xo0 + 1 == x_) {
			xo2 = 0, yo2 -= y_;
			xo3 = 0, yo3 -= y_;
		}
		int lower = -1, upper = n;
		while (upper - lower > 1) {
			int i1 = lower + upper >> 1;
			if (xxo[i1] != xo1 ? xxo[i1] > xo1 : yyo[i1] >= yo1)
				upper = i1;
			else
				lower = i1;
		}
		int i1 = upper;
		lower = -1, upper = n;
		while (upper - lower > 1) {
			int i2 = lower + upper >> 1;
			if (xxo[i2] != xo2 ? xxo[i2] > xo2 : yyo[i2] >= yo2)
				upper = i2;
			else
				lower = i2;
		}
		int i2 = upper;
		lower = -1, upper = n;
		while (upper - lower > 1) {
			int i3 = lower + upper >> 1;
			if (xxo[i3] != xo3 ? xxo[i3] > xo3 : yyo[i3] >= yo3)
				upper = i3;
			else
				lower = i3;
		}
		int i3 = upper;
		if (i1 == n || xxo[i1] > xo1 || yyo[i1] > yo1)
			continue;
		if (i2 == n || xxo[i2] > xo2 || yyo[i2] > yo2)
			continue;
		if (i3 == n || xxo[i3] > xo3 || yyo[i3] > yo3)
			continue;
		int m = 0;
		for (int i = i0; i < n && xxo[i] == xo0 && yyo[i] == yo0; i++) {
			aa[m++] = ll[i] * 8 + 0;
			aa[m++] = rr[i] * 8 + 1;
		}
		for (int i = i1; i < n && xxo[i] == xo1 && yyo[i] == yo1; i++) {
			aa[m++] = ll[i] * 8 + 2;
			aa[m++] = rr[i] * 8 + 3;
		}
		bool off = x_ && xo0 + 1 == x_;
		for (int i = i2; i < n && xxo[i] == xo2 && yyo[i] == yo2; i++) {
			aa[m++] = (ll[i] - off) * 8 + 4;
			aa[m++] = (rr[i] - off) * 8 + 5;
		}
		for (int i = i3; i < n && xxo[i] == xo3 && yyo[i] == yo3; i++) {
			aa[m++] = (ll[i] - off) * 8 + 6;
			aa[m++] = (rr[i] - off) * 8 + 7;
		}
		sort(aa, aa + m);
		int k0 = 0, k1 = 0, k2 = 0, k3 = 0;
		for (int i = 0; i + 1 < m; i++) {
			long long a_ = aa[i], a = a_ / 8;
			int t = a_ % 8;
			if (t < 0)
				a--, t += 8;
			if (t == 0)
				k0++;
			else if (t == 1)
				k0--;
			else if (t == 2)
				k1++;
			else if (t == 3)
				k1--;
			else if (t == 4)
				k2++;
			else if (t == 5)
				k2--;
			else if (t == 6)
				k3++;
			else
				k3--;
			if (k0 && k1 && k2 && k3) {
				long long b_ = aa[i + 1], b = b_ / 8;
				int s = b_ % 8;
				if (s < 0)
					b--, s += 8;
				ans += b - a;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 62 / 62