Submission #1131421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131421		lanplot	Team Contest (JOI22_team)	C++20	100 / 100	867 ms	174792 KiB

team

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (1000005)
struct node{
	ll s,e,m;
	pair<ll,ll> v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = {-1e9,s};
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll nval){
		if(s == e){
			v.first = max(v.first,nval);
		}else{
			if(x > m) r -> update(x,nval);
			else l -> update(x,nval);
			v = max(l->v,r->v);
		}
	}
	pair<ll,ll> rmq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->rmq(x,y);
			else if(y <= m) return l->rmq(x,y);
			else return max(l->rmq(x,m),r->rmq(m + 1,y));
		}
	}
} *rootBindtest, *rootCindtest, *rootBind, *rootCind;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	rootBindtest = new node(0,3*N + 5);
	rootCindtest = new node(0,3*N + 5);
	rootBind = new node(0,3*N + 5);
	rootCind = new node(0,3*N + 5);
	pair<ll,pair<ll,ll> > arr[N]; //X, Y, Z
	vector<ll> d;
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second.first>>arr[i].second.second;
		d.push_back(arr[i].first);
		d.push_back(arr[i].second.first);
		d.push_back(arr[i].second.second);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end()) - d.begin());
	for(ll i = 0;i < N;i++){
		arr[i].first = lower_bound(d.begin(),d.end(),arr[i].first) - d.begin() + 1;
		arr[i].second.first = lower_bound(d.begin(),d.end(),arr[i].second.first) - d.begin() + 1;
		arr[i].second.second = lower_bound(d.begin(),d.end(),arr[i].second.second) - d.begin() + 1;
	}
	sort(arr,arr + N);
	deque<pair<ll,pair<ll,ll> > > waiting;
	ll ans = -1e9;
	for(ll i = 0;i < N;i++){
		while(!waiting.empty() && waiting.front().first < arr[i].first){
			ll bestC = -1e9;
			if(waiting.front().second.first > 0){
				bestC = rootBindtest -> rmq(0,waiting.front().second.first - 1).first;
			}
			if(bestC != -1e9 && bestC > waiting.front().second.second){
				rootBind -> update(waiting.front().second.first,waiting.front().second.first + bestC);
			}
			
			ll bestB = -1e9;
			if(waiting.front().second.second > 0){
				bestB = rootCindtest -> rmq(0,waiting.front().second.second - 1).first;
			}
			if(bestB != -1e9 && bestB > waiting.front().second.first){
				rootCind -> update(waiting.front().second.second,waiting.front().second.second + bestB);
			}
			
			rootBindtest -> update(waiting.front().second.first,waiting.front().second.second);
			rootCindtest -> update(waiting.front().second.second,waiting.front().second.first);
			waiting.pop_front();
		}
		if(arr[i].second.first > 0){
			pair<ll,ll> maxiBind = rootBind -> rmq(arr[i].second.first + 1,3*N + 5);
			if(maxiBind.first > 0){
				ll B = maxiBind.second;
				ll C = maxiBind.first - maxiBind.second;
				if(C > arr[i].second.second){
					ans = max(ans,d[arr[i].first - 1] + d[B - 1] + d[C - 1]); //need to minus 1 cos when I discretised, I made it 1-indexed to make it easier to implement
				}
			}
		}
		if(arr[i].second.second > 0){
			pair<ll,ll> maxiCind = rootCind -> rmq(arr[i].second.second + 1,3*N + 5);
			if(maxiCind.first > 0){
				ll C = maxiCind.second;
				ll B = maxiCind.first - maxiCind.second;
				if(B > arr[i].second.first){
					ans = max(ans,d[arr[i].first - 1] + d[B - 1] + d[C - 1]); //need to minus 1 cos when I discretised, I made it 1-indexed to make it easier to implement
				}
			}
		}
		waiting.push_back(arr[i]);
	}
	if(ans == -1e9) cout<<-1<<'\n';
	else cout<<ans<<'\n';
}

/* Here is the Testcase Generator I used to debug in under 20 mins:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
pair<ll,pair<ll,ll> > arr[3]; //X, Y, Z
ll N = 3;
ll bruteforce(){
	ll ans = -1e18;
	for(ll a = 0;a < N;a++){
		for(ll b = 0;b < N;b++){
			for(ll c = 0;c < N;c++){
				if(a == b || a == c || b == c) continue;
				if(arr[a].first <= max(arr[b].first,arr[c].first)) continue;
				if(arr[b].second.first <= max(arr[a].second.first,arr[c].second.first)) continue;
				if(arr[c].second.second <= max(arr[a].second.second,arr[b].second.second)) continue;
				ans = max(ans,arr[a].first + arr[b].second.first + arr[c].second.second);
			}
		}
	}
	if(ans == -1e18) return -1;
	else return ans;
}
struct node{
	ll s,e,m,lazy;
	pair<ll,ll> v;
	node *l = nullptr,*r = nullptr; //please remember to set to nullptr (if not it might RTE)
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = {-1e18,s};
		lazy = -1e18;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propo(){
		create();
		if(lazy == -1e18) return;
		v.first = max(v.first,lazy);
		if(s != e){
			l->lazy = max(l->lazy,lazy);
			r->lazy = max(r->lazy,lazy);
		}
		lazy = -1e18;
	}
	void update(ll x,ll nval){
		if(s == e){
			lazy = max(lazy,nval);
		}else{
			create();
			if(x > m) r -> update(x,nval);
			else l -> update(x,nval);
			l->propo(), r->propo();
			v = max(l->v,r->v);
		}
	}
	pair<ll,ll> rmq(ll x,ll y){
		create();
		propo();
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->rmq(x,y);
			else if(y <= m) return l->rmq(x,y);
			else return max(l->rmq(x,m),r->rmq(m + 1,y));
		}
	}
} *rootBindtest, *rootCindtest, *rootBind, *rootCind;
ll mysol(){
	rootBindtest = new node(0,1e8 + 5);
	rootCindtest = new node(0,1e8 + 5);
	rootBind = new node(0,1e8 + 5);
	rootCind = new node(0,1e8 + 5);
	sort(arr,arr + N);
	deque<pair<ll,pair<ll,ll> > > waiting;
	ll ans = -1e18;
	for(ll i = 0;i < N;i++){
		while(!waiting.empty() && waiting.front().first < arr[i].first){
			ll bestC = -1e18;
			if(waiting.front().second.first > 0){
				bestC = rootBindtest -> rmq(0,waiting.front().second.first - 1).first;
			}
			if(bestC != -1e18){
				rootBind -> update(waiting.front().second.first,waiting.front().second.first + bestC);
			}
			
			ll bestB = -1e18;
			if(waiting.front().second.second > 0){
				bestB = rootCindtest -> rmq(0,waiting.front().second.second - 1).first;
			}
			if(bestB != -1e18){
				rootCind -> update(waiting.front().second.second,waiting.front().second.second + bestB);
			}
			
			rootBindtest -> update(waiting.front().second.first,waiting.front().second.second);
			rootCindtest -> update(waiting.front().second.second,waiting.front().second.first);
			waiting.pop_front();
		}
		if(arr[i].second.first > 0){
			pair<ll,ll> maxiBind = rootBind -> rmq(arr[i].second.first + 1,1e8 + 5);
			if(maxiBind.first > 0){
				ll C = maxiBind.first - maxiBind.second;
				if(C > arr[i].second.second){
					ans = max(ans,arr[i].first + maxiBind.first);
				}
			}
		}
		if(arr[i].second.second > 0){
			pair<ll,ll> maxiCind = rootCind -> rmq(arr[i].second.second + 1,1e8 + 5);
			if(maxiCind.first > 0){
				ll B = maxiCind.first - maxiCind.second;
				if(B > arr[i].second.first){
					ans = max(ans,arr[i].first + maxiCind.first);
				}
			}
		}
		waiting.push_back(arr[i]);
	}
	if(ans == -1e18) return -1;
	else return ans;
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll t = 100;
	while(t--){
		for(ll i = 0;i < N;i++){
			arr[i].first = rand(1,5);
			arr[i].second.first = rand(1,5);
			arr[i].second.second = rand(1,5);
		}
		ll BRUTE = bruteforce();
		ll MYSOL = mysol();
		if(BRUTE != MYSOL){
			cout<<"BRUTE: "<<BRUTE<<'\n';
			cout<<"MYSOL: "<<MYSOL<<'\n';
			for(ll i = 0;i < N;i++){
				cout<<arr[i].first<<" "<<arr[i].second.first<<" "<<arr[i].second.second<<'\n';
			}
		}
	}
	cout<<"THE END."<<'\n';
}


Found the bug from running the t=100 Testcase Generator just once:
BRUTE: -1
MYSOL: 14
1 3 5
2 5 5
4 1 1

BRUTE: -1
MYSOL: 13
3 5 2
4 5 3
5 2 1

BRUTE: -1
MYSOL: 10
1 3 3
1 5 5
2 3 1

BRUTE: -1
MYSOL: 12
3 3 1
3 3 5
4 1 1

BRUTE: -1
MYSOL: 12
2 2 4
2 4 5
4 1 1
THE END.
*/

• 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