Submission #553874

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

struct BIT{
	int tree[N];
	void add(int i, int v){ i++;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int f(int i){ i++;
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
}pre;

int a[N], pref[N];
set<int> R[N], L[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];
		pre.add(i, 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);
		R[r].erase(l);
		L[l].erase(r);
		ss.erase({l, r});
	};
	
	auto add = [&](int l, int r){
		tree.add(l, r, 1);
		R[r].insert(l);
		L[l].insert(r);
		ss.insert({l, r});
	};
	
	auto check = [&](int l, int r){
		if(a[r+1] > pre.f(r) - pre.f(l-1) && a[l-1] > pre.f(r) - pre.f(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 {
				mx = j, j = P;
			}
		}
	}
	
	// for(auto x : ss){
	// 	cout<<x[0]<<" "<<x[1]<<"\n";
	// }
	// cout<<"\n";
	
	int q; cin>>q;
	while(q--){
		//for(auto x : ss){
		//	cout<<x[0]<<" "<<x[1]<<"\n";
		//} cout<<"\n";
		
		int t; cin>>t;
		if(t == 1){
			int i, v; cin>>i>>v;
			vector<ar<int, 2>> er;
			{
				int j = par(i, 1);
				int mx = i;
				while(j-1<=n-(i == 1)){
					for(auto x : R[j-1]){
						if(i < x) break;
						er.push_back({x, j-1});
					}
					int P = p2(mx, 1);
					if(P == j){
						mx = j;
						j = par(j, 1);
					} else {
						mx = j, j = P;
					}
				}
			}
			
			for(auto x : R[i-1]){
				er.push_back({x, i-1});
			}
			
			for(auto x : L[i+1]){
				er.push_back({i+1, x});
			}
			
			for(auto x : er) del(x[0], x[1]);
			tt.sett(i, v);
			pre.add(i, -a[i] + v);
			a[i] = v;
			
			int l = par(i, 0), r = par(i, 1);
			int mx = i;
			while(1 <= l || r <= n){
				check(l+1, r-1);
				if(a[l] <= a[r]){
					int P = p2(mx, 0);
					if(P == l){
						mx = l;
						l = par(l, 0);
					} else {
						mx = l, l = P;
					}
				} else {
					int P = p2(mx, 1);
					if(P == r){
						mx = r;
						r = par(r, 1);
					} else {
						mx = r, r = P;
					}
				}
			}
			{
				int j = par(i + 1, 1);
				int mx = i + 1;
				while(j-1<=n){
					check(i+1, j-1);
					int P = p2(mx, 1);
					if(P == j){
						mx = j, j = par(j, 1);
					} else {
						mx = j, j = P;
					}
				}
			}
			
			{
				int j = par(i - 1, 0);
				int mx = i - 1;
				while(0 <= j){
					check(j+1, i-1);
					int P = p2(mx, 0);
					if(P == j){
						mx = j, j = par(j, 0);
					} else {
						mx = j, j = P;
					}
				}
			}
			
		} else {
			int l, r; cin>>l>>r;
			int L = l, R = r;
			{
				int j=par(l, 1), mx = l;
				while(j<=r){
					if(pre.f(j-1) - pre.f(l-1) < a[j]) L = j;
					int P = p2(mx, 1);
					if(P == j){
						mx = j;
						j = par(j, 1);
					} else {
						mx = j, j = P;
					}
				}
			}
			
			{
				int j=par(r, 0), mx = r;
				while(l <= j){
					if(pre.f(r)- pre.f(j) < a[j]) R = j;
					int P = p2(mx, 0);
					if(P == j){
						mx = j;
						j = par(j, 0);
					} else {
						mx = j, j = P;
					}
				}
			}
			// cout<<L<<" "<<R<<"\n";
			cout<<tree.get(L, R)[1]<<"\n";
		}
	}
}

/*

10
2 3 5 10 1 3 4 9 5 2
5
1 10 5
1 4 1000000000
1 8 20
1 4 8
2 1 10

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

*/

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