Submission #553815

#	Time	Username	Problem	Language	Result	Execution time	Memory
553815		amunduzbaev	Fish 2 (JOI22_fish2)	C++17	31 / 100	281 ms	40660 KiB

fish2

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define ar array

const int N = 1e5 + 5;
const int inf = 1e9;

struct ST{
	ar<int, 2> tree[N << 2];
	int p[N << 2];
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x<<1][0] += p[x], p[x<<1] += p[x];
		tree[x<<1|1][0] += p[x], p[x<<1|1] += p[x];
		p[x] = 0;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x][0] += v;
			p[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x<<1);
		add(l, r, v, m+1, rx, x<<1|1);
		if(tree[x<<1][0] == tree[x<<1|1][0]) tree[x] = {tree[x<<1][0], tree[x<<1][1] + tree[x<<1|1][1]};
		else tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return {N, N};
		if(lx >= l && rx <= r){
			return tree[x];
		}
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		auto L = get(l, r, lx, m, x<<1), R = get(l, r, m+1, rx, x<<1|1);
		if(L[0] == R[0]) return {L[0], L[1] + R[1]};
		else return min(L, R);
	}
	
	void build(int lx = 0, int rx = N, int x = 1){
		tree[x][1] = rx - lx + 1;
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		build(lx, m, x<<1);
		build(m+1, rx, x<<1|1);
	}
}tree;

int a[N];
int pref[N], par[N][2], p2[N][2];
int st[N][20];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	tree.build();
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pref[i] = pref[i-1] + a[i];
	}
	a[0] = a[n+1] = inf * N;
	
	for(int i=0;i<=n+1;i++) st[i][0] = a[i];
	for(int j=1;j<20;j++){
		for(int i=0;i+(1 << (j-1))<N;i++){
			st[i][j] = max(st[i][j-1], st[i+(1 << (j-1))][j-1]);
		}
	}
	
	auto get = [&](int l, int r){
		int lg = __lg(r - l + 1);
		return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
	};
	
	for(int i=1;i<=n;i++){
		{ int l = 0, r = i;
			while(l < r){
				int m = (l + r + 1) >> 1;
				if(get(m, i) > a[i]) l = m;
				else r = m - 1;
			} par[i][0] = l;
		} 
		{ int l = 0, r = i;
			while(l < r){
				int m = (l + r + 1) >> 1;
				if(get(m, i) >= a[i] * 2) l = m;
				else r = m - 1;
			} p2[i][0] = l;
		}
		{ int l = i, r = n + 1;
			while(l < r){
				int m = (l + r) >> 1;
				if(get(i, m) > a[i]) r = m;
				else l = m + 1;
			} par[i][1] = l;
		}
		{ int l = i, r = n + 1;
			while(l < r){
				int m = (l + r) >> 1;
				if(get(i, m) >= a[i] * 2) r = m;
				else l = m + 1;
			} p2[i][1] = l;
		}
	}
	
	set<ar<int, 2>> ss;
	auto del = [&](int l, int r){
		tree.add(l, r, -1);
		ss.erase({l, r});
	};
	
	auto add = [&](int l, int r){
		tree.add(l, r, 1);
		ss.insert({l, r});
	};
	
	auto check = [&](int l, int r){
		if(a[r+1] > pref[r] - pref[l-1] && a[l-1] > pref[r] - pref[l-1]){
			add(l, r);
			return true;
		} return false;
	};
	par[n+1][1] = N, par[0][0] = 0;
	for(int i=1;i<=n;i++){
		int j = par[i][1];
		int mx = i;
		while(j-1<=n-(i == 1)){
			// cout<<mx<<" "<<j<<endl;
			check(i, j-1);
			if(p2[mx][1] == j){
				mx = j;
				j = par[j][1];
			} else {
				int v = j;
				j = p2[mx][1];
				mx = v;
			}
		}
	}
	
	// for(auto x : ss){
	// 	cout<<x[0]<<" "<<x[1]<<"\n";
	// }
	// cout<<"\n";
	
	int q; cin>>q;
	while(q--){
		int t; cin>>t;
		if(t == 1){
			assert(false);
		} else {
			int l, r; cin>>l>>r;
			int L = l, R = r;
			{
				int j=par[l][1], mx = l;
				while(j<=r){
					if(pref[j-1] - pref[l-1] < a[j]) L = j;
					if(p2[mx][1] == j){
						mx = j;
						j = par[j][1];
					} else {
						int v = j;
						j = p2[mx][1];
						mx = v;
					}
				}
			}
			
			{
				int j=par[r][0], mx = r;
				while(l <= j){
					if(pref[r] - pref[j] < a[j]) R = j;
					if(p2[mx][0] == j){
						mx = j;
						j = par[j][0];
					} else {
						int v = j;
						j = p2[mx][0];
						mx = v;
					}
				}
			}
			// cout<<L<<" "<<R<<"\n";
			cout<<tree.get(L, R)[1]<<"\n";
		}
	}
}

/*

5
6 4 2 2 6
2
2 1 5 
2 1 3

*/

Compilation message (stderr)

fish2.cpp: In function 'int main()':
fish2.cpp:115:7: warning: variable 'del' set but not used [-Wunused-but-set-variable]
  115 |  auto del = [&](int l, int 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