oj.uz

Submission #569167

# Submission time Handle Problem Language Result Execution time Memory
569167 2022-05-26T20:44:10 Z mircea_007 Fountain (eJOI20_fountain) C++17
30 / 100
 64 ms 16392 KB 
// This program was written on 25.05.2022
// for problem fountain
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#include <vector>

#define MAXN 100000

int r[MAXN];
int cap[MAXN];
std::vector< std::pair<int, int> > qs[MAXN];

int qans[MAXN];

int stack[MAXN];
int psum[1 + MAXN];
int sp;

static inline int fgetint(){
  int n = 0, ch;
  
  while( !isdigit( ch = fgetc( stdin ) ) );
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( stdin ) ) );
  
  return n;
}

int main(){
  int n, q, i, j, st, dr, mij;
  
  n = fgetint();
  q = fgetint();
  for( i = n ; i-- ; ){
    r[i] = fgetint();
    cap[i] = fgetint();
  }

  for( i = 0 ; i < q ; i++ ){
    j = n - fgetint();
    qs[j].push_back( std::make_pair( fgetint(), i ) );
  }

  sp = 0;
  psum[0] = 0;
  for( i = 0 ; i < n ; i++ ){
    // update stack
    while( sp && r[stack[sp - 1]] <= r[i] )
      sp--;

    stack[sp++] = i;
    psum[sp] = psum[sp - 1] + cap[i];

    // binary search query answers
    for( auto &[vol, ansindex] : qs[i] ){
      if( vol <= psum[sp] ){
        st = 0;
        dr = sp;
        while( dr - st > 1 ){// [st, dr)
          if( psum[mij = ((st + dr) >> 1)] + vol > psum[sp] )
            dr = mij;
          else
            st = mij;
        }
        
        qans[ansindex] = n - stack[st];
      }else
        qans[ansindex] = 0;
    }
  }

  for( i = 0 ; i < q ; i++ )
    printf( "%d\n", qans[i] );
  
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2664 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 16392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2664 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Runtime error 64 ms 16392 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -