Submission #589745

#	Time	Username	Problem	Language	Result	Execution time	Memory
589745		8e7	Fish 2 (JOI22_fish2)	C++17	100 / 100	1903 ms	291412 KiB

fish2

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;

struct segtree_interval{
	stack<pii> stk[4*maxn];	
	bool in (pii &p, int x) {
		return p.ff <= x && x <= p.ss;
	}
	void remove(int cur, int l, int r, int ind, vector<pii> &v) {
		if (r <= l) return;
		while (stk[cur].size() && in(stk[cur].top(), ind)) {
			v.push_back(stk[cur].top());
			stk[cur].pop();
		}
		int m = (l + r) / 2;
		if (ind < m) remove(cur*2, l, m, ind, v);
		else if (ind > m) remove(cur*2+1, m+1, r, ind, v);
	}
	void ins(int cur, int l, int r, pii p) {
		if (r <= l) return;
		int m = (l + r) / 2;
		if (in(p, m)) {
			stk[cur].push(p);
			return;
		}
		if (m > p.ss) ins(cur*2, l, m, p);
		else if (m < p.ff) ins(cur*2+1, m+1, r, p);
	}
} inter;
struct segtree_mincnt{
	pii seg[4*maxn];
	int tag[4*maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		seg[cur].ss = (r - l);
		if (r - l == 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
	}
	void push(int cur, int l, int r) {
		seg[cur].ff += tag[cur];
		if (r - l > 1) {
			tag[cur*2] += tag[cur];
			tag[cur*2+1] += tag[cur];
		}
		tag[cur] = 0;
	}
	void merge(pii &a, pii &b, pii &c) {
		a.ff = min(b.ff, c.ff);
		a.ss = (b.ff == a.ff ? b.ss : 0) + (c.ff == a.ff ? c.ss : 0);
	}
	void pull(int cur, int l, int r) {
		int m = (l + r) / 2;
		push(cur*2, l, m), push(cur*2+1, m, r);
		merge(seg[cur], seg[cur*2], seg[cur*2+1]);
	}
	void modify(int cur, int l, int r, int ql, int qr, int v) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += v;
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v); 
		modify(cur*2+1, m, r, ql, qr, v); 
		pull(cur, l, r);
	}
	pii query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return {inf, 0};
		push(cur, l, r);
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		pii ret, vl = query(cur*2, l, m, ql, qr), vr = query(cur*2+1, m, r, ql, qr);
		merge(ret, vl, vr);
		return ret;
	}
} mincnt;

struct segtree{
	ll seg[4*maxn], tag[4*maxn];
	void init(int cur, int l, int r, ll a[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = a[l];
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, a), init(cur*2+1, m, r, a);
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	void push(int cur, int l, int r) {
		seg[cur] += tag[cur];
		if (r - l > 1) {
			tag[cur*2] += tag[cur];
			tag[cur*2+1] += tag[cur];
		}
		tag[cur] = 0;
	}
	void pull(int cur, int l, int r) {
		int m = (l + r) / 2;
		push(cur*2, l, m), push(cur*2+1, m, r);
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	void modify(int cur, int l, int r, int ql, int qr, ll x) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += x;
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, x);
		modify(cur*2+1, m, r, ql, qr, x);
		pull(cur, l, r);
	}
	int search(int cur, int l, int r, int ql, int qr, bool type, ll t) {
		//type 0: left, 1:right
		push(cur, l, r);
		if (r <= l || ql >= r || qr <= l || seg[cur] < t) return -1;
		if (r - l == 1) return l;
		int m = (l + r) / 2;
		if (type) {
			int vr = search(cur*2+1, m, r, ql, qr, type, t);
			if (vr != -1) return vr;
			return search(cur*2, l, m, ql, qr, type, t);
		} else {
			int vl = search(cur*2, l, m, ql, qr, type, t);
			if (vl != -1) return vl;
			return search(cur*2+1, m, r, ql, qr, type, t);
		}
	}
	ll query(int cur, int l, int r, int x) { //getpnt
		if (r <= l) return 0;
		push(cur, l, r);
		if (r - l == 1) return seg[cur];
		int m = (l + r) / 2;
		if (x < m) return query(cur*2, l, m, x);
		else query(cur*2+1, m, r, x);
	}
	void print(int cur, int l, int r) {
		if (r <= l) return;
		push(cur, l, r);
		if (r - l == 1) {
			debug(seg[cur]);
			return;
		}
		int m = (l + r) / 2;
		print(cur*2, l, m);
		print(cur*2+1, m, r);
	}
} tr, lb, rb; 
struct BIT{
	ll bit[maxn];
	void modify(int ind, ll val) {
		ind++;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	ll query(int ind) {
		ll ret = 0;
		ind++;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
	ll sum(int l, int r) {
		return query(r) - query(l-1);	
	}
} sum;
ll a[maxn];
int main() {
	io
	int n, q;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		sum.modify(i, a[i]);
	}
	bool ini = 1;
	auto check = [&] (int l, int r, ll s) { //stuck in [l, r]
		if (r < l) return;
		if (ini) s = sum.sum(l, r);
	
		if(!((l && s >= a[l-1]) || (r < n - 1 && s >= a[r+1]))) {
			//debug(l, r);
			inter.ins(1, 0, n, {l, r});				
			mincnt.modify(1, 0, n, l, r+1, 1);	
		}
	};
	tr.init(1, 0, n, a);
	mincnt.init(1, 0, n);
	{
		ll pref[maxn];
		for (int i = 0;i < n;i++) {
			pref[i] = a[i] + (i ? pref[i-1] : 0);
			lb.modify(1, 0, n, i, i+1, a[i] - (i ? pref[i-1] : 0));	
			rb.modify(1, 0, n, i, i+1, a[i] + pref[i]);
		}
		
		stack<int> stk;
		for (int i = 0;i < n;i++) {
			while (stk.size() && a[i] >= a[stk.top()]) {
				check(stk.top()+1, i-1, 0);
				stk.pop();	
			}
			if (stk.size()) check(stk.top()+1, i-1, 0);	
			else check(0, i-1, 0);
			stk.push(i);
		}
		while (stk.size()) {
			check(stk.top()+1, n-1, 0);
			stk.pop();
		}
	}
	ini = 0;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int i, y;
			cin >> i >> y;
			i--;
			ll d = y - a[i];
			tr.modify(1, 0, n, i, i+1, d); 
			lb.modify(1, 0, n, i, i+1, d);
			rb.modify(1, 0, n, i, i+1, d);
			lb.modify(1, 0, n, i+1, n, -d);
			rb.modify(1, 0, n, i, n, d);
			sum.modify(i, d);
			a[i] = y;

			vector<pii> rem;
			inter.remove(1, 0, n, i, rem);
			inter.remove(1, 0, n, i-1, rem);
			inter.remove(1, 0, n, i+1, rem);
			for (auto p:rem) {
				//debug("rem", p.ff, p.ss);
				mincnt.modify(1, 0, n, p.ff, p.ss+1, -1);
			}
			vector<int> lef, rig;
			int cur = i+1;		
			ll s = a[i];
			if (i+1 < n) {
				if (a[i+1] < s) s = a[i+1], cur = i+2;
				lef.push_back(i+1);
			}
			while (cur < n) {
				int nxt = tr.search(1, 0, n, cur, n, 0, s+1);
				if (nxt != -1) {
					rig.push_back(nxt-1);
					cur = nxt;
					s += a[nxt];
				} else {
					break;
				}
			}
			rig.push_back(n-1);	
			cur = i-1, s = a[i];	
			if (i-1 >= 0) {
				if (a[i-1] < s) s = a[i-1], cur = i-2;
				rig.insert(rig.begin(), i-1);
			}
			while (cur >= 0) {
				int nxt = tr.search(1, 0, n, 0, cur+1, 1, s+1);
				if (nxt != -1) {
					lef.push_back(nxt+1);
					cur = nxt;
					s += a[nxt];
				} else {
					break;
				}
			}
			lef.push_back(0);

			lef.resize(int(unique(lef.begin(), lef.end()) - lef.begin()));
			rig.resize(int(unique(rig.begin(), rig.end()) - rig.begin()));
			vector<ll> ls, rs;
			for (int I:lef) ls.push_back(sum.query(I-1)); 
			for (int I:rig) rs.push_back(sum.query(I));
			for (int I = 0;I < lef.size();I++) {
				for (int j = 0;j < rig.size();j++) {
					check(lef[I], rig[j], rs[j] - ls[I]);
				}
			}

		} else {
			int l, r;
			cin >> l >> r;
			l--; //[l, r)
			ll suml = -sum.query(l-1)+1, sumr = sum.query(r-1)+1;
			int il = lb.search(1, 0, n, l, r, 1, suml);
			int ir = rb.search(1, 0, n, l, r, 0, sumr)+1;
			if (il != -1) l = il;
			if (ir != -1) r = ir;
			cout << mincnt.query(1, 0, n, l, r).ss << "\n";
		}
	}
}
/*
*/

Compilation message (stderr)

fish2.cpp: In member function 'void segtree::print(int, int, int)':
fish2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fish2.cpp:164:4: note: in expansion of macro 'debug'
  164 |    debug(seg[cur]);
      |    ^~~~~
fish2.cpp: In function 'int main()':
fish2.cpp:299:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  299 |    for (int I = 0;I < lef.size();I++) {
      |                   ~~^~~~~~~~~~~~
fish2.cpp:300:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  300 |     for (int j = 0;j < rig.size();j++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17