Submission #1262134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262134		namhh	Team Contest (JOI22_team)	C++20	100 / 100	587 ms	32664 KiB

team

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5e4+5;
struct emilia{
	int a,b,c;
};
struct events{
	int st,x,y;
};
emilia a[N];
bool cmp(emilia a, emilia b){
	return a.a < b.a;
}
int n,val1[N],val2[N],bits[N],bits2[N],l[N],r[N];
map<int,int>mp1,mp2;
vector<events>rem;
vector<int>dm[N];
void update(int u, int val){
	while(u <= n){
		bits[u] = max(bits[u],val);
		u += u & (-u);
	}
}
int get(int u){
	int res = 0;
	while(u > 0){
		res = max(res,bits[u]);
		u -= u & (-u);
	}
	return res;
}
void update2(int u, int val){
	while(u <= n){
		bits2[u] = min(bits2[u],val);
		u += u & (-u);
	}
}
int get2(int u){
	int res = 1e9;
	while(u > 0){
		res = min(res,bits2[u]);
		u -= u & (-u);
	}
	return res;
}
// ga qua phai chef code huhu :<
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i].a >> a[i].b >> a[i].c;
		mp1[a[i].b]++;
		mp2[a[i].c]++;
	}
	int cnt = 0;
	for(auto it: mp1){
		mp1[it.fi] = ++cnt;
		val1[cnt] = it.fi;
	}
	cnt = 0;
	for(auto it: mp2){
		mp2[it.fi] = ++cnt;
		val2[cnt] = it.fi;
	}
	sort(a+1,a+n+1,cmp);
	for(int i = 1; i <= n; i++){
		a[i].b = mp1[a[i].b];
		a[i].c = mp2[a[i].c];
	}
	for(int i = 1; i <= n; i++){
		int x = get(a[i].b-1);
		if(x > a[i].c) rem.push_back({i,a[i].b,x});
		update(a[i].b,a[i].c);
	}
	for(int i = 0; i < rem.size(); i++){
		l[i] = n+1;
		int l1 = rem[i].st+1;
		int r1 = n;
		while(l1 <= r1){
			int mid = (l1+r1)/2;
			if(a[mid].a > a[rem[i].st].a){
				l[i] = mid;
				r1 = mid-1;
			}
			else l1 = mid+1;
		}
		r[i] = n;
	}
	int ans = -1;
	while(true){
		for(int i = 1; i <= n; i++){
			bits2[i] = 1e9;
			dm[i].clear();
		}
		bool ck = false;
		for(int i = 0; i < rem.size(); i++){
			int mid = (l[i]+r[i])/2;
		    if(l[i] <= r[i]){
			    dm[mid].push_back(i);
			    ck = true;
			}
		}
		if(ck == false) break;
		for(int i = n; i >= 1; i--){
			update2(a[i].b,a[i].c);
			for(int j: dm[i]){
				int st = rem[j].st;
				int x = rem[j].x;
			    int y = rem[j].y;
			    int val = get2(x-1);
			    if(val < y){
			    	ans = max(ans,a[i].a+val1[x]+val2[y]);
			    	l[j] = i+1;
			    }
			    else r[j] = i-1;
			}
		}
	}
	rem.clear();
	for(int i = 1; i <= n; i++) bits[i] = 0;
	for(int i = 1; i <= n; i++){
		int x = get(a[i].c-1);
		if(x > a[i].b) rem.push_back({i,x,a[i].c});
		update(a[i].c,a[i].b);
	}
	for(int i = 0; i < rem.size(); i++){
		l[i] = n+1;
		int l1 = rem[i].st+1;
		int r1 = n;
		while(l1 <= r1){
			int mid = (l1+r1)/2;
			if(a[mid].a > a[rem[i].st].a){
				l[i] = mid;
				r1 = mid-1;
			}
			else l1 = mid+1;
		}
		r[i] = n;
	}
	while(true){
		for(int i = 1; i <= n; i++){
			bits2[i] = 1e9;
			dm[i].clear();
		}
		bool ck = false;
		for(int i = 0; i < rem.size(); i++){
			int mid = (l[i]+r[i])/2;
		    if(l[i] <= r[i]){
			    dm[mid].push_back(i);
			    ck = true;
			}
		}
		if(ck == false) break;
		for(int i = n; i >= 1; i--){
			update2(a[i].c,a[i].b);
			for(int j: dm[i]){
				int st = rem[j].st;
				int x = rem[j].x;
			    int y = rem[j].y;
			    int val = get2(y-1);
			    if(val < x){
			    	ans = max(ans,a[i].a+val1[x]+val2[y]);
			    	l[j] = i+1;
			    }
			    else r[j] = i-1;
			}
		}
	}
	cout << ans;
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--                                              

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27