Submission #859144

#	Time	Username	Problem	Language	Result	Execution time	Memory
859144		mircea_007	Sum Zero (RMI20_sumzero)	C++17	61 / 100	262 ms	22100 KiB

sumzero

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

using ll = long long;

const int MAXN = 4e5;
const int MAXQ = 4e5;

const int INF = 1e9;

struct Range {
  int st, dr;
} ranges[1 + MAXN];
int nranges;

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

std::pair<ll, int> sp[1 + MAXN]; // { sp, idx }

// 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;

  scanf( "%d", &n );

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

    sp[i + 1].first += sp[i].first;
    sp[i + 1].second = i + 1;
  }

  std::sort( sp, sp + n + 1 );

  nranges = 0; // global pentru next_after()
  for( int i = 1 ; i < n + 1 ; i++ )
    if( sp[i - 1].first == sp[i].first )
      ranges[nranges++] = Range{ sp[i - 1].second, sp[i].second - 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] = Range{ INF, INF };
    else
      smallest_dr = ranges[i].dr;
  }

  // remove marked intervals
  nranges = std::remove_if( ranges, ranges + nranges, []( const Range &a ) -> bool {
    return a.st == INF;
  } ) - 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:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf( "%d", &n );
      |   ~~~~~^~~~~~~~~~~~
sumzero.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf( "%lld", &sp[i + 1].first );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:110:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   for( scanf( "%d", &q ) ; q-- ; ){
      |        ~~~~~^~~~~~~~~~~~
sumzero.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf( "%d%d", &qst, &qdr );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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