Performance Review (Problem G, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 2 sec
Memory limit: 256MB
Author: Jonathan Mulaywan Woenardi

# Problem Statement

Randall is a software engineer at a company with $N$ employees. Every year, the company re-evaluates its employees. At the end of every year, the company replaces its several worst-performing employees and replaces with the same number of new employees, so that the company keeps having $N$ employees. Each person has a constant performance and can be represented by an integer (higher integer means better performance), and no two people have the same performance.

The performance of the initial employees are represented by an array of integers $A = [A_1, A_2, \dots, A_N]$ where $A_i$ is the performance of the $i^{th}$ employee. Randall is employee 1, so his performance is $A_1$. We will consider the first $M$ years. At the end of the $i^{th}$ year, the company replaces its $R_i$ worst-performing employees and replaces with $R_i$ new employees. The performance of these new employees are represented by an array of integers $B_i = [(B_i)_1, (B_i)_2, \dots, (B_i)_{R_i}]$ where $(B_i)_j$ is the performance of the $j^{th}$ new employee.

He will consider $Q$ scenarios. On the $i^{th}$ scenario, he will change the value of $(B_{X_i})_{Y_i}$ to $Z_i$. For each scenario, Randall is wondering whether he will still be in the company after $M$ years. Note that the changes in each scenario are kept for the subsequent scenarios.

# Input

Input begins with a line containing three integers: $N\ M\ Q$ $(2 \leq N \leq 100\ 000;\ 1 \leq M, Q \leq 100\ 000)$ representing the number of employees, the number of years to be considered, and the number of scenarios, respectively. The next line contains $N$ integers: $A_i$ $(0 \leq A_i \leq 10^9)$ representing the performance of the initial employees. The next $M$ lines each contains several integers: $R_i$ $(B_i)_1,\ (B_i)_2,\ \cdots,\ (B_i)_{R_i}$ $(1 \leq R_i < N;\ 0 \leq (B_i)_j \leq 10^9)$ representing the number of employees replaced and the performance of the new employees, respectively. It is guaranteed that the sum of $R_i$ does not exceed $10^6$. The next $Q$ lines each contains three integers: $X_i\ Y_i\ Z_i$ $(1 \leq X_i \leq M;\ 1 \leq Y_i \leq R_{(X_i)};\ 0 \leq Z_i \leq 10^9)$ representing a scenario. It is guaranteed that all integers in all $A_i$, $(B_i)_j$, and $Z_i$ (combined together) are distinct.

# Output

For each scenario in the same order as input, output in a line an integer 0 if Randall will not be in the company after $M$ years, or 1 if Randall will still be in the company after $M$ years.

# Sample Input #1
```
5 3 3
50 40 30 20 10
4 1 2 3 100
1 4
2 6 7
1 3 300
2 1 400
2 1 5
```
# Sample Output #1
```
1
0
```
# Explanation for the sample input/output #1

Randall performance is represented by 50. For the first scenario, the value of $(B_1)_3$ is updated to 300, causes the following:

- Initially, the performance of the employees is $[50, 40, 30, 20, 10]$.
- At the end of the first year, 4 worst-performing employees are replaced by employees with performance $[300, 100, 2, 1]$. Therefore, the performance of the employees is $[300, 100, 50, 2, 1]$.
- At the end of the second year, the performance of the employees is $[300, 100, 50, 4, 2]$.
- At the end of the third year, the performance of the employees is $[300, 100, 50, 7, 6]$.

Therefore, Randall will still be in the company after 3 years.

For the second scenario, the value of $(B_2)_1$ is updated to 400, causes the following:

- Initially, the performance of the employees is $[50, 40, 30, 20, 10]$.
- At the end of the first year, the performance of the employees is $[300, 100, 50, 2, 1]$.  **Recall that the change in the first scenario is kept for this scenario as well.**
- At the end of the second year, the performance of the employees is $[400, 300, 100, 50, 2]$.
- At the end of the third year, the performance of the employees is $[400, 300, 100, 7, 6]$.

Therefore, Randall will not be in the company after 3 years.

Sample inputs:
5 3 3
50 40 30 20 10
4 1 2 3 100
1 4
2 6 7
1 3 300
2 1 400
2 1 5

Sample outputs:
1
0
1

# Solution Analysis
Analysis author: Jonathan Mulaywan Woenardi

We first observe that, if there is an employee with better performance than Randall gets replaced in a particular year, then Randall must have also been replaced at the same time or before the particular employee is replaced. Therefore, for Randall to stay in the company after $M$ years, all employees (original and newly added) who have better performance than Randall must also stay in the company after $M$ years. We only need to check for each year, whether the number of employees with better performanc...

Let $R[i]$ be the number of employees not replaced subtracted by the number of employees with better performance than Randall plus Randall itself on that particular year. Construct the initial array and check whether the minimum value of $R[i]$ for all $i$ is greater than or equal to $0$.

For each query, there are 4 possible cases:

1. The employee is previously worse than Randall. After the change, the employee is still worse than Randall.
2. The employee is previously worse than Randall. After the change, the employee is now better than Randall.
3. The employee is previously better than Randall. After the change, the employee is now worse than Randall.
4. The employee is previously better than Randall. After the change, the employee is still better than Randall.

For case 1 and case 4, since there is no change in the number of employees better than Randall joining the company each year, the answer stays the same as before the query happens.  
For case 2, the number of employees in the company better than Randall increased by 1 starting from the next year after the change until the last year.  
For case 3, the number of employees in the company better than Randall decreased by 1 starting from the next year after the change until the last year.

We can use Segment Tree with Lazy Propagation to support our update and query requirement. The query type is range minimum query and the update type is range update of $+1$ or $-1$.

The time complexity will be $O(N + (M + Q) \log M)$.


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}