Submission #1216322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216322		PenguinsAreCute	Fish 2 (JOI22_fish2)	C++17	25 / 100	4093 ms	3480 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> a) {
	int n = a.size();
	auto cmp = [&a](int x, int y) -> bool {
		if(x==-1 || y==-1)
			return (x==-1?0:1);
		return make_pair(a[x],x) < make_pair(a[y],y);
	};
	int par[n], deg[n];
	memset(par,-1,sizeof(par));
	stack<int> st;
	for(int i=0;i<n;i++) {
		while(st.size() && cmp(st.top(),i)) {
			par[st.top()] = (cmp(par[st.top()],i)?par[st.top()]:i);
			st.pop();
		}
		if(st.size())
			par[i]=st.top();
		st.push(i);
	}
	memset(deg,0,sizeof(deg));
	for(int i=0;i<n;i++)
		if(~par[i])
			deg[par[i]]++;
	int ord[n], cnt = 0;
	long long sub[n];
	for(int i=0;i<n;i++)
		sub[i] = a[i];
	for(int i=0;i<n;i++)
		for(int j=i;!deg[j];j=par[j]) {
			if(par[j]==-1)
				break;
			ord[cnt++] = j;
			deg[par[j]]--;
			deg[j]--;
			sub[par[j]] += sub[j];
		}
	bool yey[n];
	for(int i=0;i<n;i++)
		yey[i] = (~par[i]?a[par[i]]<=sub[i]:1);
	while(cnt--)
		yey[ord[cnt]] = yey[ord[cnt]] && yey[par[ord[cnt]]];
	int ans = 0;
	for(int i=0;i<n;i++)
		ans += yey[i];
	return ans;
}
int main() {
	int n, q;
	cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++)
		cin >> a[i];
	cin >> q;
	while(q--) {
		int t, y, x;
		cin >> t >> x >> y;
		if(t == 1)
			a[x-1] = y;
		else
			cout << solve(vector<int>(a.begin()+x-1,a.begin()+y)) << "\n";
	}
}

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