Submission #887476

#	Time	Username	Problem	Language	Result	Execution time	Memory
887476		Ahmed57	Team Contest (JOI22_team)	C++17	0 / 100	43 ms	7884 KiB

team

#include <bits/stdc++.h>
using namespace std;
#define int long long
int seg1[1800001],seg2[1800001];
void build(int p,int l,int r){
	seg1[p] = seg2[p] = -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,int 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,int 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]);
}
int 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));
}int 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));
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int n;
	cin>>n;
	vector<array<int,3>> v;
	map<int,int> mp,sav;
	for(int i = 0;i<n;i++){
		int 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 all = -1e9 , 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,v[ind][1]-1);
                if(val>v[ind][2]){
                	all = max(all,v[ind][1]+val);
                }
            }
            {
                long long val = query2(1,1,cnt,1,v[ind][2]-1);
                if(val>v[ind][1]){
                	all = max(all,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,all+v[i][0]);
	}
	cout<<(ans<0?-1:ans)<<endl;
}

• 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