Submission #1081448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081448		veehj	Fish 2 (JOI22_fish2)	C++17	13 / 100	4090 ms	2140 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
ll n, q;
vector<ll> a, ans;

void f(ll l, ll r){
  if(l==r){
    ans[l]=1;
    return;
  }
  ll mx=0, mxp=0;
  for(ll i=l; i<=r; i++){
    if(mx<a[i]) mx=a[i], mxp=i;
  }
  ans[mxp]=1;
  ll cnt=0;
  for(ll i=l; i<mxp; i++) cnt+=a[i];
  if(cnt>=mx) f(l, mxp-1);
  cnt=0;
  for(ll i=mxp+1; i<=r; i++) cnt+=a[i];
  if(cnt>=mx) f(mxp+1, r);
}

int main() {
  cin >> n;
  a.assign(n, -1);
  for(ll i=0; i<n; i++) cin >> a[i];
  ans.assign(n, 0);
  cin >> q;
  while(q--){
    ll t, x, y; cin >> t >> x >> y;
    if(t==1) a[x-1]=y;
    else{
      ans.assign(n, 0);
      f(x-1, y-1);
      ll cnt=0;
      for(auto& u : ans) cnt+=u;
      cout << cnt << endl;
    }
  }
}

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