Submission #859164

#	Time	Username	Problem	Language	Result	Execution time	Memory
859164		mircea_007	Sum Zero (RMI20_sumzero)	C++11	61 / 100	303 ms	20816 KiB

sumzero

#include <stdio.h>
#include <algorithm>

const int MAXN = 400000;
const int INF = 1e9;

struct Range {
  int st, dr;

  bool operator == ( const Range &that ){
    return st == that.st && dr == that.dr;
  }
} ranges[1 + MAXN];
int nranges;

const Range INF_RANGE = { INF, INF };

int next[MAXN];
int jump[MAXN];
int depth[MAXN];

long long sp[1 + MAXN];
int ord[1 + MAXN];

// primul i astfel incat ranges[i].st >= x
int next_after( int x ){
  int st = -1, dr = nranges, mij; // ranges[nranges] e santinela

  while( dr - st > 1 ){
    mij = (st + dr) >> 1;
    
    if( ranges[mij].st >= x )
      dr = mij;
    else
      st = mij;
  }

  return dr;
}

int query( int qst, int qdr ){
  int u = next_after( qst );

  int lowest = depth[u];

  while( ranges[u].dr <= qdr ){
    if( ranges[jump[u]].dr <= qdr )
      u = jump[u];
    else
      u = next[u];
  }

  return lowest - depth[u];
}

int main(){
  int n;

  //fprintf( stderr, "%ld\n", sizeof( ranges ) + sizeof( next ) + sizeof( jump ) + sizeof( depth ) + sizeof( sp ) + sizeof( ord ) );

  scanf( "%d", &n );

  sp[0] = 0;
  ord[0] = 0;
  for( int i = 1 ; i <= n ; i++ ){
    scanf( "%lld", sp + i );

    sp[i] += sp[i - 1];
    ord[i] = i;
  }

  std::sort( ord, ord + n + 1, []( int a, int b ) -> bool {
    if( sp[a] != sp[b] )
      return sp[a] < sp[b];

    return a < b;
  } );

  nranges = 0; // global pentru next_after()
  for( int i = 1 ; i < n + 1 ; i++ )
    if( sp[ord[i - 1]] == sp[ord[i]] )
      ranges[nranges++] = Range{ ord[i - 1], ord[i] - 1 };

  std::sort( ranges, ranges + nranges, []( const Range &a, const Range &b ) -> bool {
    return a.st < b.st; // nu se intampla ca a.st == b.st
  } );

  int smallest_dr = INF;
  for( int i = nranges ; i-- ; ){ // mark bad intervals
    if( ranges[i].dr > smallest_dr )
      ranges[i] = INF_RANGE;
    else
      smallest_dr = ranges[i].dr;
  }

  // remove marked intervals
  nranges = std::remove( ranges, ranges + nranges, INF_RANGE ) - ranges;

  ranges[nranges] = Range{ INF, INF };

  next[nranges] = jump[nranges] = nranges;
  depth[nranges] = 0;

  // binary lifting
  for( int i = nranges ; i-- ; ){
    int p = next_after( ranges[i].dr + 1 );

    next[i] = p;
    depth[i] = 1 + depth[p];

    if( depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]] )
      jump[i] = jump[jump[p]];
    else
      jump[i] = p;
  }

  int q;
  for( scanf( "%d", &q ) ; q-- ; ){
    int qst, qdr;

    scanf( "%d%d", &qst, &qdr );
    qst--;
    qdr--;

    printf( "%d\n", query( qst, qdr ) );
  }

  return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf( "%d", &n );
      |   ~~~~~^~~~~~~~~~~~
sumzero.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf( "%lld", sp + i );
      |     ~~~~~^~~~~~~~~~~~~~~~~~
sumzero.cpp:118:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   for( scanf( "%d", &q ) ; q-- ; ){
      |        ~~~~~^~~~~~~~~~~~
sumzero.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf( "%d%d", &qst, &qdr );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39