PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: frtransform
Testers: wuhudsm, satyam_343
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Segment trees/Fenwick trees
PROBLEM:
Alice, Bob, and Charles participated in N contests; and obtained A_i, B_i, C_i points in the i-th one, respectively.
A person gets first place in a range [L, R] of these contests if their total score in this range is not less than the score of the other two.
For each person, find the longest range of contests in which they obtained first place.
EXPLANATION:
Let’s solve the problem for Alice; the same process can be repeated for Bob and Charlie.
Consider some range [L, R] of contests.
Alice’s score is not worse than Bob’s in this range if and only if A_L + A_{L+1} + \ldots + A_R \geq B_L + B_{L+1} + \ldots + B_R.
This can be rewritten as (A_L - B_L) + (A_{L+1} - B_{L+1}) + \ldots + (A_R - B_R) \geq 0.
So, if we create an array X with X_i = A_i - B_i, we want X_L + X_{L+1} + \ldots + X_R \geq 0.
Subarray sums naturally lend themselves to prefix sums, so let’s look at those.
If pX denotes the prefix sum array of X, then we want pX_R - pX_{L-1} \geq 0, i.e, pX_R \geq pX_{L-1}.
Similarly, we can construct arrays Y and pY corresponding to A_i - C_i.
Our task is to thus find the longest range [L, R] such that pX_R \geq pX_{L-1} and pY_R \geq pY_{L-1}.
In particular, if we fix a value of R, we then want to find the smallest L \leq R such that these conditions hold.
There are ways to do this directly using persistent of 2D data structures, but there’s also a simpler solution using more well-known (and easy-to-code!) structures.
Let’s iterate over values of R in increasing order of pX_R.
This ensures that the condition pX_R \geq pX_{L-1} is automatically satisfied, so we only need to deal with L \leq R and pY_R \geq pY_{L-1}.
We now want to find the smallest value of L \leq R such that pY_R \geq pY_{L-1}.
That can be done using a segment tree and binary search, as follows:
- Consider a range-minimum segment tree built on the array pY.
- With the help of this tree, we can use binary search to find the first L in the range [1, R] whose pY_{L-1} value is no larger than pY_R.
- This can be done by querying for the minimum value in the suffix [1, \text{mid}] of the binary search and checking whether it’s below pY_R or not.
- Since we’re iterating over R in increasing order of pX_R, we can simulate this in the segment tree by first initializing everything to \infty (some large number) so that querying positions with larger pX-value doesn’t affect the minimum.
- After fixing R and finding the optimal L, update position R into the segment tree so that it can contribute to future queries.
At each index, we do a binary search which has segment tree queries within it.
This leads to a complexity of \mathcal{O}(N\log^2 N).
This can be further optimized to \mathcal{O}(N\log N) by combining the binary search into the segment tree query; in the technique sometimes known as segment tree descent or walk.
This is not necessary to get AC, however.
TIME COMPLEXITY
\mathcal{O}(N\log N) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct SegmentTree{
int n = 0;
vector<T> tree;
T neutral_element = numeric_limits<T>().max();
SegmentTree(){};
SegmentTree(int _n){
n = _n;
tree.assign(n * 4 + 5, neutral_element);
}
inline T combine(T lf, T rg){
return min(lf, rg);
}
inline void update(int v, int tl, int tr, int pos, T val){
if (tl == tr){
tree[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm){
update(v << 1, tl, tm, pos, val);
} else {
update(v << 1 | 1, tm + 1, tr, pos, val);
}
tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
}
inline void update(int pos, T val){
update(1, 0, n - 1, pos, val);
}
inline int get(int v, int tl, int tr, T val){
if (tl == tr) return tl;
int tm = (tl + tr) >> 1;
if (tree[v << 1] <= val){
return get(v << 1, tl, tm, val);
} else {
return get(v << 1 | 1, tm + 1, tr, val);
}
}
inline int get(T val){
if (tree[1] > val) return -1;
return get(1, 0, n - 1, val);
}
};
int find_longest(const vector<int> &a, const vector<int> &b, const vector<int> &c){
int n = (int)a.size();
int ans = 0;
vector<long long> x(n), y(n);
for (int i = 0; i < n; i++){
x[i] = a[i] - b[i];
y[i] = a[i] - c[i];
if (i > 0){
x[i] += x[i - 1];
y[i] += y[i - 1];
}
if (x[i] >= 0 && y[i] >= 0) ans = max(ans, i + 1);
}
vector<int> perm(n);
iota(perm.begin(), perm.end(), 0);
sort(perm.begin(), perm.end(), [&](int i, int j){
return make_tuple(x[i], y[i], i) < make_tuple(x[j], y[j], j);
});
SegmentTree<long long> st(n);
for (int i : perm){
int j = st.get(y[i]);
if (j != -1 && j < i){
ans = max(ans, i - j);
}
st.update(i, y[i]);
}
return ans;
}
void test_case(){
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
cout << find_longest(a, b, c) << ' ';
cout << find_longest(b, c, a) << ' ';
cout << find_longest(c, a, b) << endl;
}
int main(){
ios_base::sync_with_stdio(false);
int T;
cin >> T;
while (T--){
test_case();
}
return 0;
}
Tester'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 a[N],b[N],c[N],BIT[N];
ll Sx[N],Sy[N],Sz[N];
struct point
{
int num;
ll x,y;
point() {}
point(int num,ll x,ll y):num(num),x(x),y(y) {}
}P[N];
struct cmpx
{
bool operator() (point p,point q)
{
if(p.x!=q.x) return p.x<q.x;
return p.num<q.num;
}
};
struct cmpy
{
bool operator() (point p,point q)
{
if(p.y!=q.y) return p.y<q.y;
return p.num<q.num;
}
};
void modify(int p,int v)
{
for(int i=p;i<=n*2;i+=(i&-i)) BIT[i]=min(BIT[i],v);
}
int getmin(int p)
{
int mn=n;
for(int i=p;i;i-=(i&-i)) mn=min(mn,BIT[i]);
return mn;
}
int solve(int x[],int y[],int z[])
{
for(int i=1;i<=n;i++) Sx[i]=Sx[i-1]+x[i];
for(int i=1;i<=n;i++) Sy[i]=Sy[i-1]+y[i];
for(int i=1;i<=n;i++) Sz[i]=Sz[i-1]+z[i];
for(int i=0;i<=n;i++) P[i]=point(i,Sx[i]-Sy[i],Sx[i]-Sz[i]);
int ans=0;
map<ll,ll> rk;
sort(P,P+n+1,cmpy());
for(int i=0;i<=n;i++) rk[P[i].y]=i+1;
sort(P,P+n+1,cmpx());
for(int i=0;i<=n*2;i++) BIT[i]=n*2;
for(int i=0;i<=n;i++)
{
ans=max(ans,P[i].num-getmin(rk[P[i].y]));
modify(rk[P[i].y],P[i].num);
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
printf("%d ",solve(a,b,c));
printf("%d ",solve(b,a,c));
printf("%d\n",solve(c,b,a));
}
return 0;
}