oj.uz

Submission #859485

# Submission time Handle Problem Language Result Execution time Memory
859485 2023-10-10T08:24:46 Z mircea_007 Sum Zero (RMI20_sumzero) C++17
100 / 100
 345 ms 13392 KB 
// sa speram ca da override la comanda de compilare
// daca merge cu O3 atunci ar tb sa mearga si cu Os
#pragma GCC optimize( "Os" )

#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[1 + MAXN];
int jump[1 + MAXN];
int depth[1 + MAXN];

long long sp[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;
  next[0] = 0; // refolosim next
  for( int i = 1 ; i <= n ; i++ ){
    scanf( "%lld", sp + i );

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

  std::sort( next, next + 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[next[i - 1]] == sp[next[i]] )
      ranges[nranges++] = Range{ next[i - 1], next[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

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 4 ms 8676 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 4 ms 8676 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 62 ms 9660 KB Output is correct
8 Correct 63 ms 9656 KB Output is correct
9 Correct 69 ms 9812 KB Output is correct
10 Correct 66 ms 9652 KB Output is correct
11 Correct 64 ms 9656 KB Output is correct
12 Correct 72 ms 9808 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 4 ms 8676 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 62 ms 9660 KB Output is correct
8 Correct 63 ms 9656 KB Output is correct
9 Correct 69 ms 9812 KB Output is correct
10 Correct 66 ms 9652 KB Output is correct
11 Correct 64 ms 9656 KB Output is correct
12 Correct 72 ms 9808 KB Output is correct
13 Correct 310 ms 11856 KB Output is correct
14 Correct 300 ms 11384 KB Output is correct
15 Correct 345 ms 13392 KB Output is correct
16 Correct 284 ms 11880 KB Output is correct
17 Correct 308 ms 11860 KB Output is correct
18 Correct 327 ms 13356 KB Output is correct