Submission #569168

#	Time	Username	Problem	Language	Result	Execution time	Memory
569168		mircea_007	Fountain (eJOI20_fountain)	C++17	100 / 100	83 ms	13000 KiB

fountain

// 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
#define MAXQ 200000

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

int qans[MAXQ];

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40