Submission #1000557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000557		edogawa_something	Fish 2 (JOI22_fish2)	C++17	13 / 100	4083 ms	17580 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vii;
typedef pair<ll,ll> pii;
#define F first 
#define S second 
#define all(v) v.begin(),v.end()
#define pb push_back
const int M=1e5+10;
const int inf=1e9+10;
int n,a[M],q,ml[M],mr[M];
ll pre[M];
bool ans[M];
map<int,set<int>>s;
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i],s[a[i]].insert(i);
    ll q;
    cin>>q;
    while(q--){
    ll type;
    cin>>type;
    if(type==1){
    ll x,y;
    cin>>x>>y;
    x--;
    s[a[x]].erase(x);
    a[x]=y;
    s[a[x]].insert(x);
    continue;
    }
    ll l,r;
    cin>>l>>r;
    l--,r--;
    vector<int>v;
    for(int i=l;i<=r;i++){
      ml[i]=mr[i]=inf;
    }
    for(int i=l;i<=r;i++){
      while(v.size()>0&&a[i]>=a[v.back()])
      v.pop_back();
      if(v.size()>0)
      ml[i]=v.back();
      v.pb(i);
    }
    v.clear();
    for(int i=r;i>=l;i--){
      while(v.size()>0&&a[i]>=a[v.back()])
      v.pop_back();
      if(v.size()>0)
      mr[i]=v.back();
      v.pb(i);
    }
    pre[l]=0;
    for(int i=l;i<=r;i++)
    pre[i+1]=a[i]+pre[i],ans[i]=0;
    ll res=0;
    for(auto it=s.rbegin();it!=s.rend();it++){
      for(auto itt:it->S){
        if(itt>=l&&itt<=r){
        if(ml[itt]==mr[itt]&&ml[itt]==inf){
        ans[itt]=1,res++;
        continue;
        }
        if(ml[itt]==inf)
        ml[itt]=l-1;
        if(mr[itt]==inf)
        mr[itt]=r+1;
        if(ml[itt]>=l&&ans[ml[itt]])
        ans[itt]|=((pre[mr[itt]]-pre[ml[itt]+1])>=a[ml[itt]]);
        if(mr[itt]<=r&&ans[mr[itt]]){
        ans[itt]|=((pre[mr[itt]]-pre[ml[itt]+1])>=a[mr[itt]]);
        }
        res+=ans[itt];
        }
      }
    }
    cout<<res<<'\n';  
  }
}

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