Submission #887504

#	Time	Username	Problem	Language	Result	Execution time	Memory
887504		Ahmed57	Team Contest (JOI22_team)	C++17	100 / 100	1224 ms	114928 KiB

team

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long seg1[1800001],seg2[1800001];
pair<long long,long long> seg3[1800001],seg4[1800001];

void build(int p,int l,int r){
	seg1[p] = seg2[p] = -1e9;
	seg3[p] = {-1e9,-1e9};
	seg4[p] = {-1e9,-1e9};
    if(l==r){
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
}
void update1(int p,int l,int r,int idx,long long val){
	if(l==r){
		seg1[p] = max(seg1[p],val);
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update1(p*2,l,md,idx,val);
	else update1(p*2+1,md+1,r,idx,val);
	seg1[p] = max(seg1[p*2],seg1[p*2+1]);
}void update2(int p,int l,int r,int idx,long long val){
	if(l==r){
		seg2[p] = max(seg2[p],val);
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update2(p*2,l,md,idx,val);
	else update2(p*2+1,md+1,r,idx,val);
	seg2[p] = max(seg2[p*2],seg2[p*2+1]);
}void update3(int p,int l,int r,int idx,long long val2,long long val){
	if(l==r){
		seg3[p] = max(seg3[p],make_pair(val,val+val2));
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update3(p*2,l,md,idx,val2,val);
	else update3(p*2+1,md+1,r,idx,val2,val);
	seg3[p] = max(seg3[p*2],seg3[p*2+1]);
}void update4(int p,int l,int r,int idx,long long val2,long long val){
	if(l==r){
		seg4[p] = max(seg4[p],make_pair(val,val+val2));
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update4(p*2,l,md,idx,val2,val);
	else update4(p*2+1,md+1,r,idx,val2,val);
	seg4[p] = max(seg4[p*2],seg4[p*2+1]);
}
long long query1(int p,int l,int r,int lq,int rq){
	if(r<lq||l>rq||lq>rq)return -1e9;
    if(l>=lq&&r<=rq)return seg1[p];
    int md = (l+r)/2;
    return max(query1(p*2,l,md,lq,rq),query1(p*2+1,md+1,r,lq,rq));
}long long query2(int p,int l,int r,int lq,int rq){
	if(r<lq||l>rq||lq>rq)return -1e9;
    if(l>=lq&&r<=rq)return seg2[p];
    int md = (l+r)/2;
    return max(query2(p*2,l,md,lq,rq),query2(p*2+1,md+1,r,lq,rq));
}long long query3(int p,int l,int r,int lq,int rq,int limit){
	if(r<lq||l>rq||lq>rq)return -1e9;
    if(l>=lq&&r<=rq){
    	if(seg3[p].first>limit)return seg3[p].second;
    	else return -1e9;
    }
    int md = (l+r)/2;
    return max(query3(p*2,l,md,lq,rq,limit),query3(p*2+1,md+1,r,lq,rq,limit));
}long long query4(int p,int l,int r,int lq,int rq,int limit){
	if(r<lq||l>rq||lq>rq)return -1e9;
    if(l>=lq&&r<=rq){
    	if(seg4[p].first>limit)return seg4[p].second;
    	else return -1e9;
    }
    int md = (l+r)/2;
    return max(query4(p*2,l,md,lq,rq,limit),query4(p*2+1,md+1,r,lq,rq,limit));
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	vector<array<long long,3>> v;
	map<int,int> mp,sav;
	for(int i = 0;i<n;i++){
		long long a,b,c;cin>>a>>b>>c;
		v.push_back({a,b,c});
		mp[a]++;
		mp[b]++;
		mp[c]++;
	}
	int cnt = 0;
	for(auto i:mp){
		sav[i.first] = ++cnt;
	}
	sort(v.begin(),v.end());
	int ind = 0;
	long long ans = -1e9;
	build(1,1,cnt);
	for(int i = 0;i<n;i++){
        while(v[ind][0]<v[i][0]){
            {//taking first as max
                long long val = query1(1,1,cnt,1,sav[v[ind][1]]-1);
                if(val>v[ind][2]){
                	update3(1,1,cnt,sav[v[ind][1]],v[ind][1],val);
                }
            }
            {
                long long val = query2(1,1,cnt,1,sav[v[ind][2]]-1);
                if(val>v[ind][1]){
                	update4(1,1,cnt,sav[v[ind][2]],v[ind][2],val);
                }
            }
            update1(1,1,cnt,sav[v[ind][1]],v[ind][2]);
            update2(1,1,cnt,sav[v[ind][2]],v[ind][1]);
            ind++;
        }
        ans = max(ans,v[i][0]+max(query3(1,1,cnt,sav[v[i][1]]+1,cnt,v[i][2]),query4(1,1,cnt,sav[v[i][2]]+1,cnt,v[i][1])));
	}
	cout<<(ans<0?-1:ans)<<endl;
}

• 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