Submission #727416

#	Time	Username	Problem	Language	Result	Execution time	Memory
727416		model_code	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	100 / 100	1895 ms	76236 KiB

mizuyokan2

#include <cstdio>
#include <vector>
using std::pair;
using std::vector;

using std::max;
using std::min;
#include <cmath>
using std::abs;

typedef long long int ll;
typedef pair<ll, ll> P;

ll n, m, q, k;

const ll maxl = 81;

const ll base = (1LL << 18);
ll val[base];
ll jumpfrom[base];
ll exactrtol[base];
vector<P> seg[base * 2];
P seglr[base * 2];

ll findexactrtol (ll r) {
	// rightest 0 <= l <= r-2 for minor seq (l, r)
	// l >= 0, so [0, r) doesn't count
	// if (len(minor seq) <= maxl) cannot be satisfied, -1
	// O(log A)

	ll sum = 0;
	for (ll l = r - 2; l >= 0; l--) {
		sum += val[l + 1];
		if (val[l] < sum && sum > val[r]) return l;
		if (r - l - 1 > maxl) return -1;
	}
	return -1;
}

vector<ll> splitsegs (ll l, ll r) {
	// Split [l, r) into segments

	vector<ll> vecl, vecr;
	for ((l += base), (r += base); l < r; (l >>= 1), (r >>= 1)) {
		if (l % 2) {
			vecl.push_back(l);
			l++;
		}
		if (r % 2) {
			--r;
			vecr.push_back(r);
		}
	}

	vector<ll> res = vecl;
	for (ll j = vecr.size() - 1; j >= 0; j--) res.push_back(vecr[j]);
	return res;
}

vector<P> resetseg (ll v) {
	// recalc seg[v] from seg[v * 2 + 0], seg[v * 2 + 1]

	ll sl = seglr[v].first, sr = seglr[v].second;
	ll sm = (sl + sr) / 2;
	ll vl = v * 2 + 0, vr = v * 2 + 1;

	vector<P> res;
	for (ll j = 0; j < maxl; j++) {
		ll l = sl + j;
		if (l >= sr) break;

		ll xr = l, xcnt = 0;
		if (l < sm) {
			P pl = seg[vl][j];
			ll l2 = jumpfrom[pl.first];
			if (l2 < sr) {
				P pr = seg[vr][l2 - sm];

				xr = pr.first;
				xcnt = pl.second + 1 + pr.second;
			} else {
				xr = pl.first;
				xcnt = pl.second;
			}
		} else {
			xr = seg[vr][l - sm].first;
			xcnt = seg[vr][l - sm].second;
		}

		res.emplace_back(xr, xcnt);
	}

	seg[v] = res;
	return res;
}
void init () {
	for (ll i = n; i < base; i++) {
		val[i] = 1;
	}

	// exactrtol, jumpfrom
	for (ll r = 0; r < base; r++) {
		exactrtol[r] = findexactrtol(r);
		// if (r < n) fprintf(stderr, "e %lld: %lld\n", r, exactrtol[r]);
	}
	for (ll l = base - 1; l >= 0; l--) {
		jumpfrom[l] = base;
		for (ll r = l; r < base; r++) {
			if (exactrtol[r] >= l) {
				jumpfrom[l] = r;
				break;
			}
		}
		// if (l < n) fprintf(stderr, "j %lld: %lld\n", l, jumpfrom[l]);
	}

	// seglr, seg
	for (ll i = 0; i < base; i++) {
		seglr[base + i] = (P){i, i + 1};

		vector<P> segl;
		segl.emplace_back(i, 0LL);
		seg[base + i] = segl;
	}
	for (ll i = base - 1; i >= 1; i--) {
		seglr[i] = (P){
			seglr[i * 2 + 0].first,
			seglr[i * 2 + 1].second,
		};

		seg[i] = resetseg(i);
	}
}
void update (ll x, ll y) {
	val[x] = y;

	// Update exactrtol, jumpfrom BEFORE seg!
	for (ll r = x; r < x + maxl + 5; r++) {
		if (r >= base) break;
		exactrtol[r] = findexactrtol(r);
		// if (r < n) fprintf(stderr, "e %lld: %lld\n", r, exactrtol[r]);
	}
	for (ll l = x; l > x - maxl - 5; l--) {
		if (l < 0) break;

		jumpfrom[l] = base; // if no
		for (ll r = l; r < base; r++) {
			if (exactrtol[r] >= l) {
				jumpfrom[l] = r;
				break;
			}
		}
		// if (l < n) fprintf(stderr, "j %lld: %lld\n", l, jumpfrom[l]);
	}

	// Update seg[l, l] and then the above
	vector<P> segl;
	segl.emplace_back(x, 0LL);
	ll v = x + base;
	seg[v] = segl;
	while (v /= 2) {
		resetseg(v);
	}
}

ll solve2 (ll l, ll r) {
	// [l, r], both val[l] and val[r] are in minor seq
	// counts major seq

	if (l > r) return -(n + 5);

	vector<ll> segs = splitsegs(l, r + 1);

	ll result = 0;
	ll v = l;
	for (ll segid : segs) {
		ll sl = seglr[segid].first;
		ll sr = seglr[segid].second;

		if (sr <= v) continue;

		P p = seg[segid][v - sl];
		v = p.first;
		result += p.second;

		if (jumpfrom[v] <= r) {
			v = jumpfrom[v];
			result++;
		} else {
			break;
		}
	}

	return result;
}
ll solve (ll l, ll r) {

	ll result = 1; // Eliminate "no minor seq"
	ll sum;

	// [ ], [ ), ( ], ( )
	ll lj; // |[-)
	sum = 0;
	for (lj = l + 1; lj < r; lj++) {
		sum += val[lj - 1];
		if (sum > val[lj]) break;
	}
	ll rj; // (-]|
	sum = 0;
	for (rj = r - 2; rj >= l; rj--) {
		sum += val[rj + 1];
		if (sum > val[rj]) break;
	}

	result = max(result, solve2(l, r - 1) * 2 + 1);
	result = max(result, solve2(lj, r - 1) * 2 + 2);
	result = max(result, solve2(l, rj) * 2 + 2);
	result = max(result, solve2(lj, rj) * 2 + 3);

	return result;
}

int main (void) {
	scanf("%lld", &n);
	for (ll i = 0; i < n; i++) {
		scanf("%lld", &val[i]);
	}
	scanf("%lld", &q);
	init();
	for (ll i = 0; i < q; i++) {
		ll x, y, a, b;
		scanf("%lld%lld%lld%lld", &x, &y, &a, &b);
		--x;

		update(x, y);
		printf("%lld\n", solve(a, b));
	}
}

Compilation message (stderr)

mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:224:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:226:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |   scanf("%lld", &val[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
mizuyokan2.cpp:228:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |  scanf("%lld", &q);
      |  ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:232:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |   scanf("%lld%lld%lld%lld", &x, &y, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 32 / 32
• Subtask 5: 29 / 29
• Subtask 6: 11 / 11