제출 #1282509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282509		bobtheguy	Team Contest (JOI22_team)	C++20	0 / 100	110 ms	6112 KiB

team

#include<bits/stdc++.h>
using namespace std;
 const long long N=4*1e5,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;
 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));
}
void calibrate(long long idx,long long val){
    if (idx<pos){
        long long x=get(1,1,N,1,pos-1).mx;
        update(1,1,N,idx,val);
        long long new_x=get(1,1,N,1,pos-1).mx;

        if (new_x>x){
            long long l=1,r=N;
            while (l<=r){
                long long mid=(l+r)/2;
                long long ca1=get(1,1,N,mid,N).mn;
                if (new_x>ca1) l=mid+1;
                else r=mid-1;
            }
            if (l<1||l>N) return;
            pos=l;
        }
    }
    else{
        long long old_x=get(1,1,N,pos,N).mn,old_mx=get(1,1,N,1,idx).mx;
        update(1,1,N,idx,val);
        long long new_x=get(1,1,N,pos,N).mn,new_mx=get(1,1,N,1,idx).mx;
        if (old_x>new_x){
            if (get(1,1,N,idx,N).mn<get(1,1,N,1,idx-1).mx) pos=idx;
        }
        else if (old_mx<new_mx){
            long long l=1,r=N;
            while (l<=r){
                long long mid=(l+r)/2;
                long long ca1=get(1,1,N,mid,N).mn;
                if (new_mx>ca1) l=mid+1;
                else r=mid-1;
            }
            if (l<1||l>N) return;
            pos=l;
        }
    }
}
signed main(){
    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;
    }
    pos=1;
    for (i=1;i<=n;i++){
        if (p[i].x!=p[i-1].x){
            while (j+1<i){
                j++;
                calibrate(p[j].y,p[j].z);
            }
        }
        if (p[i].y>=pos) continue;
        long long x=get(1,1,N,1,pos-1).mx;
        if (x>get(1,1,N,pos,N).mn){
            if (x>p[i].z) ans=max(ans,p[i].x+vec[pos-1]+x);
        }

    }
    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