Submission #589691

#	Time	Username	Problem	Language	Result	Execution time	Memory
589691		8e7	Fish 2 (JOI22_fish2)	C++17	31 / 100	468 ms	289368 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, 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);
	}
} 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]);
	}
	auto check = [&] (int l, int r) { //stuck in [l, r]
		if (r < l) return;
		ll 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);
				stk.pop();	
			}
			if (stk.size()) check(stk.top()+1, i-1);	
			else check(0, i-1);
			stk.push(i);
		}
		while (stk.size()) {
			check(stk.top()+1, n-1);
			stk.pop();
		}
	}
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			cout << "zisk" << "\n";
		} 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;
			debug("query", l, r);
			cout << mincnt.query(1, 0, n, l, r).ss << "\n";
		}
	}
}
/*
*/

Compilation message (stderr)

fish2.cpp: In lambda function:
fish2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fish2.cpp:191:4: note: in expansion of macro 'debug'
  191 |    debug(l, r);
      |    ^~~~~
fish2.cpp: In function 'int main()':
fish2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fish2.cpp:236:4: note: in expansion of macro 'debug'
  236 |    debug("query", l, r);
      |    ^~~~~

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