Submission #721318

#	Time	Username	Problem	Language	Result	Execution time	Memory
721318		Abrar_Al_Samit	Fish 2 (JOI22_fish2)	C++17	13 / 100	4069 ms	8204 KiB

fish2

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

const int nax = 1e5 + 3;


struct BIT {
	long long bit[nax] = {0};

	void update(int i, int val) {
		while(i<nax) {
			bit[i] += val;
			i += i&-i;
		}
	}
	long long query(int i) {
		long long ret = 0;
		while(i>0) {
			ret += bit[i];
			i -= i&-i;
		}
		return ret;
	}
	long long query(int l, int r) {
		return query(r) - query(l-1);
	}
};
long long a[nax];
int n;
bool wins[nax];
void PlayGround() {

	BIT T;
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
		T.update(i, a[i]);
	}

	int q;
	cin>>q;	
	while(q--) {
		int tp;
		cin>>tp;
		if(tp==1) {
			int x, y;
			cin>>x>>y;
			T.update(x, y-a[x]);
			a[x] = y;
		} else {
			int l, r;
			cin>>l>>r;

			vector<int>ids;
			for(int i=l; i<=r; ++i) {
				ids.push_back(i);
				wins[i] = 0;
			}
			sort(ids.begin(), ids.end(), [&] (int i, int j) {
				return make_pair(a[i], i) > make_pair(a[j], j);
			});	

			set<int>cr = {l-1, r+1};
			for(int j : ids) {
				int lef = *(--cr.lower_bound(j));
				int rit = *cr.lower_bound(j);
				long long S = T.query(lef+1, rit-1);

				if(lef < l && rit > r) {
					wins[j] = 1;
				} 
				if(lef >= l) {
					if(a[lef] <= S) wins[j] = wins[lef];
				}
				if(rit <= r) {
					if(a[rit] <= S) wins[j] = wins[rit];
				} 
				cr.insert(j);
			}
			int ans = 0;
			for(int i=l; i<=r; ++i) {
				ans += wins[i];
			}
			cout<<ans<<'\n';
		}
	}

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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