Submission #1262132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262132		namhh	Team Contest (JOI22_team)	C++20	0 / 100	2 ms	3912 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){
		bits[u] = min(bits[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});
		if(a[i].a != a[i+1].a){
			for(int j = i; j >= 1; j--){
				if(a[j].a != a[i].a) break;
		        update(a[j].b,a[j].c);
		    }
		}
	}
	for(int i = 0; i < rem.size(); i++){
		l[i] = rem[i].st+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--){
			for(int j: dm[i]){
				int st = rem[j].st;
				int x = rem[j].x;
			    int y = rem[j].y;
			    int val1 = get2(x-1);
			    if(val1 < y) l[j] = i;
			    else r[j] = i-1;
			}
			if(a[i].a != a[i-1].a){
				for(int j = i; j <= n; j++){
					if(a[j].a != a[i].a) break;
					update2(a[j].b,a[j].c);
				}
			}
		}
	}
	int ans = -1;
	for(int i = 0; i < rem.size(); i++){
		if(l[i] >= 1 && l[i] <= n) ans = max(ans,a[l[i]].a+val1[rem[i].x]+val2[rem[i].y]);
	}
	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});
		if(a[i].a != a[i+1].a){
			for(int j = i; j >= 1; j--){
				if(a[j].a != a[i].a) break;
		        update(a[j].c,a[j].b);
		    }
		}
	}
	for(int i = 0; i < rem.size(); i++){
		l[i] = rem[i].st+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--){
			for(int j: dm[i]){
				int st = rem[j].st;
				int x = rem[j].x;
			    int y = rem[j].y;
			    int val1 = get2(y-1);
			    if(val1 < x) l[j] = i;
			    else r[j] = i-1;
			}
			if(a[i].a != a[i-1].a){
				for(int j = i; j <= n; j++){
					if(a[j].a != a[i].a) break;
					update2(a[j].c,a[j].b);
				}
			}
		}
	}
	for(int i = 0; i < rem.size(); i++){
		if(l[i] >= 1 && l[i] <= n) ans = max(ans,a[l[i]].a+val1[rem[i].x]+val2[rem[i].y]);
	}
	cout << ans;
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--                                     ..::---====---::.                              

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