Submission #1282507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282507		bobtheguy	Team Contest (JOI22_team)	C++20	64 / 100	2095 ms	6128 KiB

team

#include<bits/stdc++.h>
using namespace std;
 const long long value=1e18;
struct grp{
    long long x,y,z;
} p[2*100010];
struct node{
    long long mn=value,mx=-value;
} st[8*100010];
 long long i,n,j=0,ans=-1,pos=1,N;
 vector<long long> vec;
 bool flag=0;
node merge_node(const node& A,const node& B){
    if (A.mx<0) return B;
    if (B.mx<0) return A;
    return {min(A.mn,B.mn),max(A.mx,B.mx)};
}
void update(long long id,long long l,long long r,long long u,long long x){
    if (r<u||u<l) return;
    if (l>=r){
        st[id].mn=min(st[id].mn,x);
        st[id].mx=max(st[id].mx,x);
        return;
    }
    long long mid=(l+r)/2;
    update(2*id,l,mid,u,x);
    update(2*id+1,mid+1,r,u,x);
    st[id]=merge_node(st[2*id],st[2*id+1]);
}
node get(long long id,long long l,long long r,long long u,long long v){
    if (u>v) return {value,-value};
    if (r<u||v<l) return {value,-value};
    if (u<=l&&r<=v) return st[id];
    long long mid=(l+r)/2;
    return merge_node(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
long long bs(long long x){
    for (long long i=N;i>=x;i--){
        if (get(1,1,N,1,i-1).mx>get(1,1,N,i,N).mn) return i;
    }
    return -1;
}
signed main(){
    //freopen("team.inp","r",stdin);
    //freopen("team.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for (i=1;i<=n;i++) cin>>p[i].x>>p[i].y>>p[i].z;
    sort(p+1,p+n+1,[](const grp& A,const grp& B){
            return A.x<B.x;
    });
    long long j=0;
    for (i=1;i<=n;i++){
        vec.push_back(p[i].y);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for (i=1;i<=n;i++){
        p[i].y=lower_bound(vec.begin(),vec.end(),p[i].y)-vec.begin()+1;
    }
    N=vec.size();
    pos=1;
    for (i=1;i<=n;i++){
        //cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].z<<"\n";
        if (p[i].x!=p[i-1].x){
            while (j+1<i){
                j++;
                update(1,1,N,p[j].y,p[j].z);
            }
        }

        long long ca=bs(p[i].y+1);
        if (ca<0) continue;
        long long x=get(1,1,N,1,ca-1).mx;
        if (p[i].z<x) ans=max(ans,p[i].x+vec[ca-1]+x);

    }
    cout<<ans;
}

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