Submission #758048

#	Time	Username	Problem	Language	Result	Execution time	Memory
758048		maomao90	Tortoise (CEOI21_tortoise)	C++17	100 / 100	631 ms	37664 KiB

tortoise

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 500005;

int n;
int a[MAXN];
int lft[MAXN], rht[MAXN];
int grp[MAXN], lstgrp[MAXN], prvgrp[MAXN];
bool done[MAXN], donewalk[MAXN];
ll ans;

int fw[MAXN];
void fincre(int i, int x) {
	i++;
	for (; i <= n; i += i & -i) {
		fw[i] += x;
	}
}
void fincre(int s, int e, int x) {
	fincre(s, x);
	fincre(e + 1, -x);
}
int fqsm(int i) {
	i++;
	int res = 0;
	for (; i > 0; i -= i & -i) {
		res += fw[i];
	}
	return res;
}

#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
int st[MAXN * 4], lz[MAXN * 4];
void propo(int u, int lo, int hi) {
	if (lz[u] == 0) {
		return;
	}
	MLR;
	st[lc] += lz[u];
	lz[lc] += lz[u];
	st[rc] += lz[u];
	lz[rc] += lz[u];
	lz[u] = 0;
}
void upd(int p, int x, int u = 1, int lo = 0, int hi = n - 1) {
	if (lo == hi) {
		st[u] = x;
		return;
	}
	MLR;
	propo(u, lo, hi);
	if (p <= mid) {
		upd(p, x, lc, lo, mid);
	} else {
		upd(p, x, rc, mid + 1, hi);
	}
	st[u] = min(st[lc], st[rc]);
}
void incre(int s, int e, int x, int u = 1, int lo = 0, int hi = n - 1) {
	if (s > e) {
		return;
	}
	if (lo >= s && hi <= e) {
		st[u] += x;
		lz[u] += x;
		return;
	}
	MLR;
	propo(u, lo, hi);
	if (s <= mid) {
		incre(s, e, x, lc, lo, mid);
	}
	if (e > mid) {
		incre(s, e, x, rc, mid + 1, hi);
	}
	st[u] = min(st[lc], st[rc]);
}
int qmn(int s, int e, int u = 1, int lo = 0, int hi = n - 1) {
	if (s > e) {
		return INF;
	}
	if (lo >= s && hi <= e) {
		return st[u];
	}
	MLR;
	propo(u, lo, hi);
	int res = INF;
	if (s <= mid) {
		mnto(res, qmn(s, e, lc, lo, mid));
	}
	if (e > mid) {
		mnto(res, qmn(s, e, rc, mid + 1, hi));
	}
	return res;
}

ii st2[MAXN * 4];
int lz2[MAXN * 4];
void propo2(int u, int lo, int hi) {
	if (lz2[u] == 0) {
		return;
	}
	MLR;
	st2[lc].FI += lz2[u];
	lz2[lc] += lz2[u];
	st2[rc].FI += lz2[u];
	lz2[rc] += lz2[u];
	lz2[u] = 0;
}
void upd2(int p, int x, int u = 1, int lo = 0, int hi = n - 1) {
	if (lo == hi) {
		st2[u] = {x, lo};
		return;
	}
	MLR;
	propo2(u, lo, hi);
	if (p <= mid) {
		upd2(p, x, lc, lo, mid);
	} else {
		upd2(p, x, rc, mid + 1, hi);
	}
	st2[u] = min(st2[lc], st2[rc]);
}
void incre2(int s, int e, int x, int u = 1, int lo = 0, int hi = n - 1) {
	if (s > e) {
		return;
	}
	if (lo >= s && hi <= e) {
		st2[u].FI += x;
		lz2[u] += x;
		return;
	}
	MLR;
	propo2(u, lo, hi);
	if (s <= mid) {
		incre2(s, e, x, lc, lo, mid);
	}
	if (e > mid) {
		incre2(s, e, x, rc, mid + 1, hi);
	}
	st2[u] = min(st2[lc], st2[rc]);
}
ii qmn2(int s, int e, int u = 1, int lo = 0, int hi = n - 1) {
	if (s > e) {
		return {INF, INF};
	}
	if (lo >= s && hi <= e) {
		return st2[u];
	}
	MLR;
	propo2(u, lo, hi);
	ii res = {INF, INF};
	if (s <= mid) {
		mnto(res, qmn2(s, e, lc, lo, mid));
	}
	if (e > mid) {
		mnto(res, qmn2(s, e, rc, mid + 1, hi));
	}
	return res;
}

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n;
	ll tot = 0;
	REP (i, 0, n) {
		cin >> a[i];
		if (a[i] > 0) {
			tot += a[i];
		}
	}
	int prv = -INF;
	int gc = 0;
	REP (i, 0, n) {
		if (a[i] == -1) {
			prv = i;
			gc++;
		}
		lft[i] = prv;
		grp[i] = gc;
	}
	prv = INF;
	RREP (i, n - 1, 0) {
		if (a[i] == -1) {
			prv = i;
		}
		rht[i] = prv;
	}
	vi id, pos;
	prv = -1;
	REP (i, 0, n) {
		if (a[i] == -1) {
			lstgrp[grp[i] - 1] = prv;
		}
		if (a[i] <= 0) {
			continue;
		}
		id.pb(i);
		pos.pb(i);
		prv = i;
	}
	sort(ALL(id), [&] (int l, int r) {
			return ii{min(l - lft[l], rht[l] - l), -l} < 
			ii{min(r - lft[r], rht[r] - r), -r};
			});
	REP (i, 1, n) {
		fincre(i, n - 1, 1);
	}
	REP (i, 0, n) {
		upd(i, INF);
		upd2(i, INF);
	}
	REP (i, 0, gc + 1) {
		if (lstgrp[i] == -1 || grp[lstgrp[i]] != i) {
			continue;
		}
		upd2(lstgrp[i], lstgrp[i]);
	}
	memset(prvgrp, -1, sizeof prvgrp);
	for (int i : id) {
		cerr << i << '\n';
		done[i] = 1;
		int w = 2 * min(i - lft[i], rht[i] - i);
		// x <= a[i]
		int mn = qmn(i + 1, n - 1);
		assert(mn >= 0);
		// x * w <= mn
		// x <= floor(mn / w)
		int x1 = mn / w;
		int ct = fqsm(i);
		if (ct > 2 * i) {
			continue;
		}
		bool delta = 0;
		if (i - lft[i] <= rht[i] - i) { // left cycle
			if (donewalk[grp[i]]) {
				continue;
			}
			auto apply = [&] (int x, bool walk) {
				if (x + walk == 0) {
					return;
				}
				delta = 1;
				donewalk[grp[i]] |= walk;
				cerr << "APPLY: " << x << ' ' << walk << '\n';
				ans += x + walk;
				fincre(i, n - 1, x * w);
				incre(i, n - 1, -x * w);
				incre2(i, n - 1, -x * w);
				// ct + (x - 1) * w + upd <= 2 * i
				assert(ct + (x - 1 + walk) * w <= 2 * i);
				upd(i, 2 * i - (ct + (x - 1 + walk) * w));
			};
			// ct + (x - 1) * w <= 2 * i
			// x <= (2 * i - ct) / w + 1
			int x2 = (2 * i - ct) / w + 1;
			if (a[i] < min(x1, x2)) {
				auto ptr = upper_bound(ALL(pos), i);
				bool walk = 0;
				if (ptr == pos.end() || grp[*ptr] != grp[i] || done[*ptr]) {
					walk = 1;
				}
				if (donewalk[grp[i]]) {
					walk = 0;
				}
				apply(a[i] - walk, walk);
				if (a[i] + walk) {
					prvgrp[grp[i]] = i;
				}
			} else if (rht[i] == INF) {
				apply(min(x1, x2), 0);
				if (min(x1, x2)) {
					prvgrp[grp[i]] = i;
				}
			} else if (x1 < x2) { // stopped by suffix but still have extra for walk
				auto ptr = upper_bound(ALL(pos), i);
				bool walk = 0;
				if (ptr == pos.end() || grp[*ptr] != grp[i] || done[*ptr]) {
					walk = 1;
				}
				if (donewalk[grp[i]]) {
					walk = 0;
				}
				if (a[i] == x1 && walk) {
					apply(x1 - 1, 1);
				} else {
					apply(x1, walk);
				}
			} else {
				// no extra for walk unless replace one cycle with walk
				int nct = ct + x2 * w;
				// nct + j - i <= 2 * j
				// nct - i <= j
				int j = nct - i;
				auto ptr = lower_bound(ALL(pos), j);
				bool walk = 0;
				if (ptr == pos.end() || grp[*ptr] != grp[i] || done[*ptr]) {
					walk = 1;
				}
				if (donewalk[grp[i]]) {
					walk = 0;
				}
				apply(x2 - walk, walk);
			}
		} else { // right cycle
			auto apply = [&] (int x) {
				if (x == 0) {
					return;
				}
				delta = 1;
				cerr << "APPLY: " << x << '\n';
				ans += x;
				fincre(i, n - 1, x * w);
				incre(i, n - 1, -x * w);
				incre2(i, n - 1, -x * w);
				// ct + x * w + upd <= 2 * i
				assert(ct + x * w <= 2 * i);
				upd(i, 2 * i - (ct + x * w));
			};
			auto ptr = lower_bound(ALL(pos), i);
			bool walk = 0;
			if (ptr == pos.begin() || grp[*prev(ptr)] != grp[i] || 
					done[*prev(ptr)] || fqsm(*prev(ptr)) > 2 * (*prev(ptr))) {
				walk = 1;
			}
			if (donewalk[grp[i]]) {
				walk = 0;
			}
			if (walk) {
				cerr << "WALK\n";
				donewalk[grp[i]] = 1;
				a[i]--;
				ans++;
				// ct + upd <= 2 * i
				upd(i, 2 * i - ct);
			} else if (!donewalk[grp[i]]) {
				assert(lstgrp[grp[i]] == i);
				upd2(i, INF);
				lstgrp[grp[i]] = *prev(ptr);
				int ct = fqsm(*prev(ptr));
				upd2(*prev(ptr), 2 * (*prev(ptr)) - ct);
			}
			// ct + x * w <= 2 * i
			// x <= (2 * i - ct) / w
			int x2 = (2 * i - ct) / w;
			apply(min({a[i], x1, x2}));
		}
		while (st2[1].FI < 0) {
			int u = st2[1].SE, g = grp[u], v = prvgrp[g];
			upd2(u, INF);
			if (donewalk[g]) {
				continue;
			}
			cerr << "HI " << u << ' ' << g << ' ' << v << '\n';
			if (v == -1) {
				continue;
			}
			donewalk[g] = 1;
			int w = 2 * min(v - lft[v], rht[v] - v);
			if (v - lft[v] <= rht[v] - v) {
				fincre(v + 1, n - 1, -w);
				incre(v + 1, n - 1, w);
				incre2(v + 1, n - 1, w);
			} else {
				fincre(v, n - 1, -w);
				incre(v, n - 1, w);
				incre2(v, n - 1, w);
			}
		}
		if (delta) {
			prvgrp[grp[i]] = i;
		}
	}
	cout << tot - ans << '\n';
	return 0;
}

Compilation message (stderr)

tortoise.cpp: In function 'void propo(int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:70:2: note: in expansion of macro 'MLR'
   70 |  MLR;
      |  ^~~
tortoise.cpp:64:17: warning: unused variable 'mid' [-Wunused-variable]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
tortoise.cpp:70:2: note: in expansion of macro 'MLR'
   70 |  MLR;
      |  ^~~
tortoise.cpp: In function 'void upd(int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:82:2: note: in expansion of macro 'MLR'
   82 |  MLR;
      |  ^~~
tortoise.cpp: In function 'void incre(int, int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:100:2: note: in expansion of macro 'MLR'
  100 |  MLR;
      |  ^~~
tortoise.cpp: In function 'int qmn(int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:117:2: note: in expansion of macro 'MLR'
  117 |  MLR;
      |  ^~~
tortoise.cpp: In function 'void propo2(int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:135:2: note: in expansion of macro 'MLR'
  135 |  MLR;
      |  ^~~
tortoise.cpp:64:17: warning: unused variable 'mid' [-Wunused-variable]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
tortoise.cpp:135:2: note: in expansion of macro 'MLR'
  135 |  MLR;
      |  ^~~
tortoise.cpp: In function 'void upd2(int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:147:2: note: in expansion of macro 'MLR'
  147 |  MLR;
      |  ^~~
tortoise.cpp: In function 'void incre2(int, int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:165:2: note: in expansion of macro 'MLR'
  165 |  MLR;
      |  ^~~
tortoise.cpp: In function 'ii qmn2(int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:182:2: note: in expansion of macro 'MLR'
  182 |  MLR;
      |  ^~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 25 / 25
• Subtask 5: 27 / 27