# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

**Setter:** TheScrasse

**Preparer:** Aryan Agarwala

**Tester:** Harris Leung

**Editorialist:** Trung Dang

# DIFFICULTY:

1815

# PREREQUISITES:

Prefix sum

# PROBLEM:

There are N people (numbered from 1 to N). One of these people is a thief and always lies, the others are honest people and always tell the truth.

Person i claims that the thief is one of l_i, l_{i+1}, l_{i+2}, \cdots, r_i.

How many people could be the thief?

# EXPLANATION:

Letâ€™s iterate through each person and check if they could be a thief or not. For the person i to be a thief, two conditions must satisfy:

- The range that this person provide must not include i, i.e. i \notin [l_i, r_i]
- For every other person, the range that they provide must include i, i.e. i \in [l_j, r_j] for all j \neq i.

The first condition is easy to check on the fly, but we need to transform the second condition a bit. That condition is equivalent to: the intersection of the ranges of every other person must include i. This leads us to this observation:

- If we compute the â€śprefixâ€ť intersection (just as we compute the prefix sum of an array), as well as the â€śsuffixâ€ť intersection, then we can easily find out the intersection of every person that isnâ€™t i (simply take the intersection of prefix i - 1 and suffix i + 1).

This gives us the solution:

- We first precompute the prefix intersection and the suffix intersection.
- Then for each person i, we check the first condition, then compute the intersection of prefix i - 1 and suffix i + 1 and check whether this range includes i.

# TIME COMPLEXITY:

Time complexity is O(N) for each test case.

# SOLUTION:

## Tester's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=1e9+7;
typedef pair<int,int> pii;
int n;
pii a[100001];
pii pf[100002],sf[100002];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
cin >> n;
pf[0]=sf[n+1]={1,n};
for(int i=1; i<=n ;i++){
cin >> a[i].fi >> a[i].se;
pf[i].fi=max(pf[i-1].fi,a[i].fi);
pf[i].se=min(pf[i-1].se,a[i].se);
}
for(int i=n; i>=1 ;i--){
sf[i].fi=max(sf[i+1].fi,a[i].fi);
sf[i].se=min(sf[i+1].se,a[i].se);
}
int ans=0;
for(int i=1; i<=n ;i++){
int l=max(pf[i-1].fi,sf[i+1].fi);
int r=min(pf[i-1].se,sf[i+1].se);
if(l<=i && i<=r && (i<a[i].fi || i>a[i].se)) ans++;
}
cout << ans << '\n';
for(int i=1; i<=n ;i++){
int l=max(pf[i-1].fi,sf[i+1].fi);
int r=min(pf[i-1].se,sf[i+1].se);
if(l<=i && i<=r && (i<a[i].fi || i>a[i].se)) cout << i << '\n';
}
}
}
```

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
pair<int, int> add(pair<int, int> a, pair<int, int> b) {
return {max(a.first, b.first), min(a.second, b.second)};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<pair<int, int>> a(n), pre(n), suf(n);
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
partial_sum(a.begin(), a.end(), pre.begin(), add);
partial_sum(a.rbegin(), a.rend(), suf.rbegin(), add);
vector<int> ans;
for (int i = 0; i < n; i++) {
pair<int, int> xd = {1, n};
if (i > 0) {
xd = add(xd, pre[i - 1]);
}
if (i + 1 < n) {
xd = add(xd, suf[i + 1]);
}
if (i + 1 >= xd.first && i + 1 <= xd.second
&& (i + 1 < a[i].first || i + 1 > a[i].second)) {
ans.push_back(i + 1);
}
}
cout << ans.size() << '\n';
for (int v : ans) {
cout << v << '\n';
}
}
}
```