CHEFMALA - Editorial

Setter: Ashley Khoo
Tester: Harris Leung
Editorialist: Trung Dang

Medium-Hard

PREREQUISITES:

Segment Tree, Segment Tree Beats

PROBLEM:

Chef is preparing a banquet of N dishes for Sir Anton and Sir Trygub. Unfortuantely, Sir Anton and Sir Trygub only told the Chef three days before the banquet that they do not like food that is too spicy or too numb.

For the i-th dish, Chef has assigned 4 scores:

• SA_i — the spiciness felt by Sir Anton
• NA_i — the numbness felt by Sir Anton
• ST_i — the spiciness felt by Sir Trygub
• NT_i — the numbness felt by Sir Trygub

Find the minimum value of \max\limits_{i \in A}(SA_i)+\max\limits_{i \in A}(NA_i)+\max\limits_{i \in T}(ST_i)+\max\limits_{i \in T}(NT_i) over all (A,T), such that, A \subseteq [1,N],T \subseteq [1,N], 1 \leq |A|,|T| and A \cup T = [1,N].

EXPLANATION:

We perform the following strategy:

• Fix the values of \max\limits_{i \in A}(SA_i) and \max\limits_{i \in A}(NA_i). Denote the fixed values as MSA and MNA respectively.
• For all dishes j such that SA_j \le MSA and NA_j \le MNA, put them into A.
• The remaining dishes are put into T.

This strategy leads to an obvious O(N^3) algorithm:

• Loop over MSA.
• Loop over MSB.
• Construct the set T according to the previous strategy.
• Calculate \max\limits_{i \in T}(ST_i) and \max\limits_{i \in T}(NT_i).

To speed up this process, we use the following strategy:

• Let MNA be the index of some data structure D, where D_{MNA} stores MNA+\max\limits_{i \in T}(ST_i)+\max\limits_{i \in T}(NT_i), where T is the set of dishes j that have SA_j > MSA and NA_j > MNA.
• Sweep line over decreasing MSA.
• When we reach some dish i such that SA_i = MSA, update the data structure D for indices from NA_i + 1 to \infty. Specifically, we need to update the values of \max\limits_{i \in T}(ST_i) and \max\limits_{i \in T}(NT_i) for these indices.
• Then we query the minimum value of D.

We can see that this data structure needs to support maximizing range update and max range query. There are multiple ways to do this:

• Apply direct segment tree beats.
• Precompute using stacks to transform each maximizing range update to many addition range updates (this strategy is used in the setter’s solution).

TIME COMPLEXITY:

Time complexity is O(N \log^2 N) per test case.

SOLUTION:

Setter's Solution
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
int s,e,m;
int val=0,lazy=0;
node *l,*r;

node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;

if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}

void propo(){
if (lazy){
val+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
}

void update(int i,int j,int k){
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);

l->propo(),r->propo();
val=min(l->val,r->val);
}
}

int query(int i,int j){
propo();
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return min(l->query(i,m),r->query(m+1,j));
}
} *root;

int n;
vector<tuple<int,int,int,int> > v;

int arr[200005];
int brr[200005];
int crr[200005];
int drr[200005];

vector<ii> stkc;
vector<ii> stkd;

bool alive[200005];

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int TC;
cin>>TC;
while (TC--){
cin>>n;
v.clear();
root=new node(0,n);
stkc.clear();
stkd.clear();

int A,B,C,D;
rep(x,0,n){
cin>>A>>B>>C>>D;
v.pub({A,B,C,D});
}

sort(all(v));

rep(x,0,n) tie(arr[x],brr[x],crr[x],drr[x])=v[x];

//corner case: pick 1 only
vector<int> a(arr,arr+n),b(brr,brr+n);
sort(all(a)); reverse(all(a));
sort(all(b)); reverse(all(b));

int ans=1e18;
rep(x,0,n) ans=min(ans,a[arr[x]==a[0]]+b[brr[x]==b[0]]+crr[x]+drr[x]);

stkc.pub({0,n});
stkd.pub({0,n});
root->update(n,n,arr[n-1]);

int currc=0,currd=0;

rep(x,n,0){
currc=max(currc,crr[x]);
currd=max(currd,drr[x]);
stkc.pub({currc,x});
stkd.pub({currd,x});

root->update(x,x,(x?arr[x-1]:0)+currc+currd);
}

reverse(all(stkc));
reverse(all(stkd));

vector<int> idx;
rep(x,0,n) idx.pub(x);
sort(all(idx),[](int i,int j){
return brr[i]<brr[j];
});

ans=min(ans,root->query(1,n-1)+brr[idx[n-1]]);

rep(x,0,n) alive[x]=true;
int pos=0;

rep(x,n,1){
alive[idx[x]]=false;
int c=crr[idx[x]],d=drr[idx[x]];

while (stkc.back().fi<c){
auto temp=stkc.back(); stkc.pob();
root->update(stkc.back().se+1,temp.se,c-temp.fi);
}
if (stkc.back().se!=n) stkc.pub({c,n});

while (stkd.back().fi<d){
auto temp=stkd.back(); stkd.pob();
root->update(stkd.back().se+1,temp.se,d-temp.fi);
}
if (stkd.back().se!=n) stkd.pub({d,n});

while (!alive[pos]) pos++;
ans=min(ans,root->query(pos+1,n)+brr[idx[x-1]]);
}

cout<<ans<<endl;
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}
const int N=2e5+2;
int n;
ll a1[N],a2[N],b1[N],b2[N];
pair<ll,int>s1[N];
pair<ll,int>s2[N];
int p1[N],p2[N];
ll m11[N],m12[N],m21[N],m22[N];
ll f[N][4];
ll mn[1<<19][4];
void build(int id,int l,int r){
if(l==r){
for(int i=0; i<4 ;i++) mn[id][i]=f[l][i];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
for(int i=0; i<4 ;i++) mn[id][i]=min(mn[id*2][i],mn[id*2+1][i]);
}
ll qry(int t,int id,int l,int r,int ql,int qr){
if(l>qr || r<ql) return 1e18;
if(ql<=l && r<=qr) return mn[id][t];
int mid=(l+r)/2;
return min(qry(t,id*2,l,mid,ql,qr),qry(t,id*2+1,mid+1,r,ql,qr));
}
ll mini(ll x,ll y){
//cout << y << endl;
return min(x,y);
}
int tot=2e5;
void solve(){
tot-=n;
for(int i=1; i<=n ;i++){
s1[i]={a1[i],i};
s2[i]={a2[i],i};
}
sort(s1+1,s1+n+1);sort(s2+1,s2+n+1);
for(int i=1; i<=n ;i++){
p1[s1[i].se]=i;
p2[s2[i].se]=i;
}
for(int i=0; i<4 ;i++) f[n+1][i]=s2[n].fi;
m11[n+1]=m12[n+1]=m21[n+1]=m22[n+1]=0;
for(int i=n; i>=1 ;i--){
int x=s1[i].se,y=s2[i].se;
m11[i]=max(m11[i+1],b1[x]);
m12[i]=max(m12[i+1],b2[x]);
m21[i]=max(m21[i+1],b1[y]);
m22[i]=max(m22[i+1],b2[y]);
f[i][0]=s2[i-1].fi;
f[i][1]=s2[i-1].fi+m21[i];
f[i][2]=s2[i-1].fi+m22[i];
f[i][3]=s2[i-1].fi+m21[i]+m22[i];
//cout << m11[i] << ' ' << m12[i] <<' ' << m21[i] << ' ' << m22[i] << '\n';
}
build(1,1,n+1);
ll ans=1e18;
int lb=n+1;
for(int i=1; i<=n ;i++){
//cout << "solve " << i << endl;
ll c1=m11[i+1],c2=m12[i+1];
lb=min(lb,p2[s1[i].se]+1);
int u1,u2;
{
int l=1,r=n+1;
while(l!=r){//find smallest i st m21[i]<=c1
int mid=(l+r)/2;
if(m21[mid]>c1) l=mid+1;
else r=mid;
}
u1=l;
}
{
int l=1,r=n+1;
while(l!=r){//find smallest i st m22[i]<=c2
int mid=(l+r)/2;
if(m22[mid]>c2) l=mid+1;
else r=mid;
}
u2=l;
}
//cout << u1 << ' ' << u2 << endl;
{
int l=max(u1,u2);
int r=n+1;
if(i==n) r=min(r,n);
l=max(l,lb);
if(l<=r){
ll fk=qry(0,1,1,n+1,l,r);
ans=mini(ans,fk+c1+c2+s1[i].fi);
}
}
{
int l=u2;
int r=u1-1;
if(i==n) r=min(r,n);
l=max(l,lb);
if(l<=r){
ll fk=qry(1,1,1,n+1,l,r);
ans=mini(ans,fk+c2+s1[i].fi);
}
}
{
int l=u1;
int r=u2-1;
if(i==n) r=min(r,n);
l=max(l,lb);
if(l<=r){
ll fk=qry(2,1,1,n+1,l,r);
ans=mini(ans,fk+c1+s1[i].fi);
}
}
{
int l=1;
int r=min(u1-1,u2-1);
if(i==n) r=min(r,n);
l=max(l,lb);
if(l<=r){
ll fk=qry(3,1,1,n+1,l,r);
ans=mini(ans,fk+s1[i].fi);
}
}
}
ll ma1=0,ma2=0,mb1=0,mb2=0;
for(int i=1; i<=n ;i++){
ma1=max(ma1,a1[i]);
ma2=max(ma2,a2[i]);
mb1=max(mb1,b1[i]);
mb2=max(mb2,b2[i]);
}
for(int i=1; i<=n ;i++){
ans=mini(ans,ma1+ma2+b1[i]+b2[i]);
ans=mini(ans,a1[i]+a2[i]+mb1+mb2);
}

cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);