Submission #572056

#	Time	Username	Problem	Language	Result	Execution time	Memory
572056		gs14004	Fish 2 (JOI22_fish2)	C++17	0 / 100	4027 ms	8128 KiB

fish2

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 100005;

lint a[MAXN];

struct node{
	int s, e, cost;
	bool operator<(const node &nd)const{
		return pi(s, -e) < pi(nd.s, -nd.e);
	}
	bool operator==(const node &nd)const{
		return pi(s, -e) == pi(nd.s, -nd.e);
	}
};

struct bit{
	lint tree[MAXN];
	void add(int x, lint v){
		for(int i = x; i < MAXN; i += i & -i) tree[i] += v;
	}
	lint query(int x){
		lint ret = 0;
		for(int i = x; i; i -= i & -i) ret += tree[i];
		return ret;
	}
	lint query(int s, int e){
		if(s > e) return 0;
		return query(e) - query(s - 1);
	}
}bit, subs;

int n;
set<node> st;

void getNodeSet(int x, vector<node> &v){
	if(x < 2 || x >= n) return;
	int l = x, r = x;
	while(true){
		lint curSum = bit.query(l, r);
		if(curSum < min(a[l-1], a[r+1])){
			v.push_back({l, r, -1});
			if(l == 2 && r == n - 1) break;
			if(a[l-1] < a[r+1]) l--;
			else r++;
		}
		curSum = bit.query(l, r);
		int leftClosest = 0, rightClosest = n + 1;
		for(int i = l - 1; i > 0; i--){
			if(a[i] > curSum){
				leftClosest = i;
				break;
			}
		}
		for(int i = r + 1; i <= n; i++){
			if(a[i] > curSum){
				rightClosest = i;
				break;
			}
		}
		l = leftClosest + 1;
		r = rightClosest - 1;
	}
}

void add(int x, int v){
	vector<node> l;
	getNodeSet(x-1, l);
	getNodeSet(x, l);
	getNodeSet(x+1, l);
	sort(all(l));
	reverse(all(l));
	l.resize(unique(all(l)) - l.begin());
	for(auto &x : l){
		auto it = st.lower_bound({x.s, x.e, -1});
		if(it != st.end() && it->s == x.s && it->e == x.e){
			//			cout << "erase interval " << x.s << " " << x.e << " " << it->cost << endl;
			subs.add(it->s - 1, -it->cost);
			st.erase(it);
		}
		else assert(0);
	}
	l.clear();
	bit.add(x, v);
	a[x] += v;
	getNodeSet(x-1, l);
	getNodeSet(x, l);
	getNodeSet(x+1, l);
	sort(all(l));
	reverse(all(l));
	l.resize(unique(all(l)) - l.begin());
	for(auto &x : l){
		auto it = st.lower_bound({x.s, x.e, -1});
		if(it != st.end() && it->s == x.s && it->e == x.e){
			assert(0);
		}
		int sum = subs.query(x.s - 1, x.e);
		subs.add(x.s - 1, x.e - x.s + 1 - sum);
		st.insert({x.s, x.e, x.e - x.s + 1 - sum});
		//		cout << "Add interval " << x.s << " " << x.e << " " << x.e - x.s + 1 - sum << endl;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	a[1] = a[n + 2] = 1e15;
	for(int i = 2; i <= n + 1; i++){
		cin >> a[i];
	}
	n += 2;
	for(int i = 1; i <= n; i++){
		bit.add(i, a[i]);
	}
	for(int i = 2; i <= n - 1; i++){
		vector<node> l;
		getNodeSet(i, l);
		for(auto &x : l){
			auto it = st.lower_bound({x.s, x.e, -1});
			if(it != st.end() && it->s == x.s && it->e == x.e){
				subs.add(it->s - 1, -it->cost);
				st.erase(it);
			}
			int sum = subs.query(x.s - 1, x.e);
			subs.add(x.s - 1, x.e - x.s + 1 - sum);
			st.insert({x.s, x.e, x.e - x.s + 1 - sum});
			//		cout << "Add interval " << x.s << " " << x.e << " " << x.e - x.s + 1 - sum << endl;
		}
	}
	int q; cin >> q;
	while(q--){
		int t, x, y; cin >> t >> x >> y;
		if(t == 1){
			x++;
			add(x, y - a[x]);
		}
		else{
			x++; y++;
			int sx = x, sy = y;
			for(int i = x; i <= y; i++){
				if(bit.query(x, i - 1) < a[i]) sx = i;
			}
			for(int i = y; i >= x; i--){
				if(bit.query(i + 1, y) < a[i]) sy = i;
			}
			cout << sy - sx + 1 - subs.query(sx, sy - 1) << "\n";
		}
	}
}

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