Submission #553850

#	Time	Username	Problem	Language	Result	Execution time	Memory
553850		amunduzbaev	Fish 2 (JOI22_fish2)	C++17	31 / 100	1106 ms	16844 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;

struct ST2{
	int tree[N<<2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) {
			tree[x] = v; 
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	int get_l(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(tree[x] >= v){
				if(lx == rx) return lx;
				int m = (lx + rx) >> 1;
				if(tree[x<<1] >= v) return get_l(l, r, v, lx, m, x<<1);
				else return get_l(l, r, v, m+1, rx, x<<1|1);
			} else return -1;
		} int m = (lx + rx) >> 1;
		int res = get_l(l, r, v, lx, m, x<<1);
		if(~res) return res;
		return get_l(l, r, v, m+1, rx, x<<1|1);
	}
	
	int get_r(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(tree[x] >= v){
				if(lx == rx) return lx;
				int m = (lx + rx) >> 1;
				if(tree[x<<1|1] >= v) return get_r(l, r, v, m+1, rx, x<<1|1);
				else return get_r(l, r, v, lx, m, x<<1);
			} else return -1;
		} int m = (lx + rx) >> 1;
		int res = get_r(l, r, v, m+1, rx, x<<1|1);
		if(~res) return res;
		return get_r(l, r, v, lx, m, x<<1);
	}
}tt;

int a[N], pref[N];

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;
	a[n+2] = a[n+1] + 1;
	for(int i=0;i<N;i++){
		tt.sett(i, a[i]);
	}
	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;
	};
	
	auto par = [&](int i, int d){
		if(d){
			return tt.get_l(i, N, a[i] + 1);
		} else {
			return tt.get_r(0, i, a[i] + 1);
		}
	};
	auto p2 = [&](int i, int d){
		if(d){
			return tt.get_l(i, N, a[i] * 2);
		} else {
			return tt.get_r(0, i, a[i] * 2);
		}
	};
	
	for(int i=1;i<=n;i++){
		int j = par(i, 1);
		int mx = i;
		while(j-1<=n-(i == 1)){
			// cout<<"here"<<endl;
			check(i, j-1);
			int P = p2(mx, 1);
			if(P == j){
				mx = j;
				j = par(j, 1);
			} else {
				int v = j;
				j = P;
				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);
			int i, v; cin>>i>>v;
			auto it = ss.lower_bound({i+1, 0});
			
		} 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;
					int P = p2(mx, 1);
					if(P == j){
						mx = j;
						j = par(j, 1);
					} else {
						int v = j;
						j = P;
						mx = v;
					}
				}
			}
			
			{
				int j=par(r, 0), mx = r;
				while(l <= j){
					if(pref[r] - pref[j] < a[j]) R = j;
					int P = p2(mx, 0);
					if(P == j){
						mx = j;
						j = par(j, 0);
					} else {
						int v = j;
						j = P;
						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:177:9: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  177 |    auto it = ss.lower_bound({i+1, 0});
      |         ^~
fish2.cpp:116:7: warning: variable 'del' set but not used [-Wunused-but-set-variable]
  116 |  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