Submission #735086

#	Time	Username	Problem	Language	Result	Execution time	Memory
735086		NemanjaSo2005	Mizuyokan 2 (JOI23_mizuyokan2)	C++14	0 / 100	446 ms	4252 KiB

mizuyokan2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,Q,niz[250005],res[250005];
int main(){
   cin>>N;
   for(int i=1;i<=N;i++)
      cin>>niz[i];
   cin>>Q;
   while(Q--){
      ll a,b,L,R;
      cin>>a>>b>>L>>R;
      L++;
      niz[a]=b;
      res[R]=1;
      for(int i=R-1;i>=L;i--){
         ll suma=0;
         for(int j=i+1;j<=R;j++){
            if(niz[j]<suma and niz[i]<suma)
               res[i]=max(res[i],res[j]+2);
            suma+=niz[j];
         }
         if(suma>niz[i])
            res[i]=max(res[i],2ll);
      }
      ll r=max(res[L],1ll);
      ll suma=niz[L];
      for(int i=L+1;i<=R;i++){
         if(suma>niz[i])
            r=max(res[i]+1,r);
         suma+=niz[i];
      }
      cout<<r<<endl;
   }
   return 0;
}
/*
4
6 2 3 2
1
3 2 1 3

5
1 2 3 4 5
3
1 1 1 2
1 1 1 5
1 1 0 5
*/

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11