# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* wuhudsm

*iceknight1093*

**Tester & Editorialist:**# DIFFICULTY:

2723

# PREREQUISITES:

Simple dynamic programming, basic data structure knowledge — for example `set`

s

# PROBLEM:

N people order takeout, the i-th person’s order will be ready at time X_i and he will arrive to collect it at time Y_i. X_i \lt Y_i is known.

Each person will:

- Take his order if it’s present.
- If his order is not present but some others are, take whichever present order has the lowest
*index*. - Do nothing if no orders are present.

An *evil person* is one who takes an order that isn’t his.

A devil can steal exactly one person’s order. What’s the maximum possible number of evil people?

# EXPLANATION:

The main observation required to solve this problem is the following: at any moment of time, at most one order (that should be present at this time) will be missing.

## Proof

Suppose the devil steals person i's order that’s supposed to be ready at time X_i; and the person arrives at time Y_i.

Then,

- At any time before X_i, everything is as it should be
- At times in the range [X_i, Y_i-1],
*almost*everything is as it should be: the only difference is that person i's order is missing. - At time Y_i:
- If there are no orders present, nothing happens and person i leaves.

Note that if the devil hadn’t stolen his order, then in the normal process there would be no orders remaining at the end of this time anyway; which means the process will go on as usual after Y_i and no more orders will be missing. - If there is an order present, person i will take it. Suppose he takes order j.

Then, at times in the range [Y_i+1, Y_j-1], person j's order will be the only one missing (everything else is accounted for, and person i's order would normally have been taken at time Y_i anyway)

- If there are no orders present, nothing happens and person i leaves.
- Continue this process to see that at any instant, at most one order is missing.

Note that in the last case in the above proof, the process during time [Y_i+1, Y_j-1] proceeds exactly the same as if the devil had stolen person j's order initially!

This observation leads us to a solution.

Let \text{take}[i] denote the index of the takeout that person i will take, if his own is missing (and \text{take}[i] = -1 if no such person exists).

Note that since at most one order is missing at any time, \text{take}[i] is uniquely defined.

Now, if the devil steals person i's takeout, it’s easy to see that the people who become angry form a chain, going as i \to \text{take}[i] \to \text{take}[\text{take}[i]] \to \ldots, as long as the next person exists (i.e doesn’t equal -1).

This tells us that we need to compute two things: the \text{take}[i] values for each i, and then the longest chain in them.

## Computing take

Let’s attempt to find \text{take}[i].

If person i's takeout is missing, then at time Y_i we know that all remaining takeouts will be of persons j such that X_j \lt Y_i \lt Y_j, i.e, takeouts that were prepared before Y_i but weren’t taken yet.

We want to find the smallest j such that this condition is satisfied, and do so for *every* i.

If no such j exists, then \text{take}[i] = -1 of course.

Note that the problem constraints guarantee that all the X_i and Y_j are distinct between 1 and 2N, which means something (in fact, exactly one thing) happens at each time instant.

Let’s use that fact to simulate the process nicely:

- Iterate across time, from 1 to 2N. Also maintain a set of takeouts that haven’t been taken yet, say S.
- At time t,
- If there’s an i such that X_i = t, insert i into S.
- If there’s an i such that Y_i = t, delete i from S.

Then, (if S is non-empty) \text{take}[i] will be the smallest element of S.

At each time instant, we do only a couple of operations at most.

So, if S were a data structure that allowed us to quickly insert and erase elements, as well as get the smallest element, we’d be done.

There is indeed such a data structure: a `set`

(`std::set`

in C++, `TreeSet`

in Java, Python unfortunately doesn’t have one built-in).

This allows us to insert/delete elements in \mathcal{O}(\log N), and get the minimum element in \mathcal{O}(1).

So, make S a set and simulate the process as mentioned above, for \mathcal{O}(N\log N) runtime.

## Finding the longest chain

Once the \text{take}[i] values are known, finding the longest chain is fairly straightforward.

Let \text{dp}[i] be the length of the longest chain if the devil steals person i's takeout.

Then,

- If \text{take}[i] = -1, we have \text{dp}[i] = 0
- Otherwise, \text{take}[i] = 1 + \text{dp}[\text{take}[i]]

As long as memoization is used, computing this for every i takes \mathcal{O}(N) time.

The answer is just the maximum of the \text{dp} array.

# TIME COMPLEXITY

\mathcal{O}(N \log N) per test case.

# CODE:

## Author's code (C++)

```
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int steal[N],dp[N];
struct Data
{
int t,num,ty;
Data() {}
Data(int t,int num,int ty):t(t),num(num),ty(ty) {}
friend bool operator<(Data x,Data y)
{
return x.t<y.t;
}
}d[N];
void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
d[i]=Data(t,i,0);
}
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
d[n+i]=Data(t,i,1);
}
sort(d+1,d+2*n+1);
}
void solve()
{
int ans=0;
set<int> S;
for(int i=1;i<=n;i++) dp[i]=steal[i]=0;
for(int i=1;i<=n*2;i++)
{
if(d[i].ty)
{
S.erase(d[i].num);
if(!S.empty()) steal[d[i].num]=*S.begin();
}
else S.insert(d[i].num);
}
for(int i=n*2;i;i--)
{
if(d[i].ty&&steal[d[i].num])
{
dp[d[i].num]=dp[steal[d[i].num]]+1;
ans=max(ans,dp[d[i].num]);
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)
{
init();
solve();
}
return 0;
}
```

## Editorialist's code (Python)

```
import heapq
for _ in range(int(input())):
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
event = [0]*(2*n + 1)
take = [-1]*n
for i in range(n):
event[x[i]] = i+1
event[y[i]] = -(i+1)
active = []
for i in range(1, 2*n+1):
id = abs(event[i]) - 1
if event[i] > 0:
heapq.heappush(active, (id, y[id]))
else:
while active:
if active[0][1] <= i: heapq.heappop(active)
else: break
if active: take[id] = active[0][0]
dp = [0]*n
for i in reversed(range(1, 2*n+1)):
id = abs(event[i]) - 1
if event[i] < 0:
if take[id] != -1: dp[id] = 1 + dp[take[id]]
print(max(dp))
```