Submission #152320

#	Time	Username	Problem	Language	Result	Execution time	Memory
152320		Kalam	Bigger segments (IZhO19_segments)	C++11	0 / 100	16 ms	16120 KiB

segments

// 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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27