oj.uz

Submission #569168

# Submission time Handle Problem Language Result Execution time Memory
569168 2022-05-26T20:44:57 Z mircea_007 Fountain (eJOI20_fountain) C++17
100 / 100
 83 ms 13000 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
#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.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 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7152 KB Output is correct
2 Correct 56 ms 10624 KB Output is correct

Subtask #3
40.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 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 52 ms 7152 KB Output is correct
9 Correct 56 ms 10624 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 36 ms 7344 KB Output is correct
12 Correct 83 ms 13000 KB Output is correct
13 Correct 77 ms 12536 KB Output is correct
14 Correct 67 ms 11780 KB Output is correct
15 Correct 78 ms 12092 KB Output is correct