Submission #1069251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069251		raduv	Fountain (eJOI20_fountain)	C++14	100 / 100	114 ms	17236 KiB

fountain

  #include <stdio.h>
  #include <utility>
  #include <ctype.h>
  const int MAXN = 100'000;
  const int LOG = 18;
  using namespace std;
  int rmq[LOG + 1][MAXN + 1], cap[LOG + 1][MAXN + 1];
  pair<int, int> stiva[MAXN + 1];
  int ns;
  static inline int getInt(){
    int n = 0, ch;
    while(!isdigit(ch = getc(stdin)));
    do
      n = n * 10 + ch - '0';
    while (isdigit(ch = getc(stdin)));
    return n;
  }
  int main()
  {
      int n, q, i, diam, p, a, b;
      n = getInt();
      q = getInt();
      for( i = 1; i <= n; i++ ){
        diam = getInt();
        cap[0][i] = getInt();
        while(ns > 0 && diam > stiva[ns].first)
          rmq[0][stiva[ns--].second] = i;
        stiva[++ns] = {diam, i};
      }
      while(ns > 0)
        rmq[0][stiva[ns--].second] = i;
      for ( p = 1; p <= LOG; p++ ){
        for( i = 1; i <= n; i++ ){
          rmq[p][i] = rmq[p - 1][rmq[p - 1][i]];
          cap[p][i] = cap[p - 1][i] + cap[p - 1][rmq[p - 1][i]];
        }
      }
      while(q--){
        a = getInt();
        b = getInt();
        for( i = LOG; i >= 0; i-- ){
          if(cap[i][a] < b){
            b -= cap[i][a];
            a = rmq[i][a];
          }
        }
        printf("%d\n", a);
      }
      return 0;
  }

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40