oj.uz

Submission #735086

# Submission time Handle Problem Language Result Execution time Memory
735086 2023-05-03T13:28:35 Z NemanjaSo2005 Mizuyokan 2 (JOI23_mizuyokan2) C++14
0 / 100
 446 ms 4252 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 446 ms 3440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 395 ms 4252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -