oj.uz

Submission #152320

# Submission time Handle Problem Language Result Execution time Memory
152320 2019-09-07T13:30:16 Z Kalam Bigger segments (IZhO19_segments) C++11
0 / 100
 16 ms 16120 KB 
// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 500000 + 77;
int n , A[N] , P[N];
long long a[N] , S[N] , Mn[N << 2];
void Update(int x , int l = 1 , int r = n + 1 , int id = 1) {
   if(r - l < 2) {
      Mn[id] = a[l] + S[l];
      return ;
   }
   int mid = ((l + r) >> 1);
   if(x < mid) Update(x , l , mid , id << 1);
   else Update(x , mid , r , id << 1 ^ 1);
   Mn[id] = min(Mn[id << 1] , Mn[id << 1 ^ 1]);
}
int Get(int ql , int qr , long long x , int l = 1 , int r = n + 1 , int id = 1) {
   if(qr <= l || r <= ql || Mn[id] > x) return 0;
   if(r - l < 2) return l;
   int mid = ((l + r) >> 1);
   if(Mn[id << 1 ^ 1] < x) return Get(ql , qr , x , mid , r , id << 1 ^ 1);
   return Get(ql , qr , x , l , mid , id << 1);
}
int main() {
   memset(Mn , 63 , sizeof Mn);
   scanf("%d" , & n);
   for(int i = 1;i <= n;++ i) scanf("%lld" , a + i) , a[i] += a[i - 1];
   A[1] = P[1] = 1;
   S[1] = a[1];
   Update(1);
   for(int i = 2;i <= n;++ i) {
      A[i] = A[i - 1];
      P[i] = P[i - 1];
      S[i] = S[i - 1] + a[i] - a[i - 1];
      // check if answer can be improved
      int id = Get(P[i - 1] , i , a[i]);
      if(P[i] <= id) {
         ++ A[i];
         P[i] = i;
         S[i] = a[i] - a[id];
      }
      Update(i);
   }
   printf("%d\n" , A[n]);
   return 0;
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & n);
    ~~~~~^~~~~~~~~~~~
segments.cpp:29:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    for(int i = 1;i <= n;++ i) scanf("%lld" , a + i) , a[i] += a[i - 1];
                               ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16120 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 16 ms 15996 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Incorrect 15 ms 15992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16120 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 16 ms 15996 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Incorrect 15 ms 15992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16120 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 16 ms 15996 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Incorrect 15 ms 15992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16120 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 16 ms 15996 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Incorrect 15 ms 15992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16120 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 16 ms 15996 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Incorrect 15 ms 15992 KB Output isn't correct
6 Halted 0 ms 0 KB -