제출 #791119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791119		winter0101	Team Contest (JOI22_team)	C++14	9 / 100	125 ms	22380 KiB

team

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
const int maxn=1e5+4e5+9;
struct tup{
int x,y,z;
bool operator < (const tup& p){
return x<p.x;
}
}a[maxn];
int n;
int ans=-1;
int rx[maxn],ry[maxn],rz[maxn];
void nenso(){
    vector<int>n1,n2,n3;
    n1.pb(0),n2.pb(0),n3.pb(0);
    for1(i,1,n){
    n1.pb(a[i].x);
    n2.pb(a[i].y);
    n3.pb(a[i].z);
    }
    sort(all(n1)),sort(all(n2)),sort(all(n3));
    map<int,int>m1,m2,m3;
    for1(i,1,n){
    if (n1[i]>n1[i-1]){
        m1[n1[i]]=m1[n1[i-1]]+1;
        rx[m1[n1[i]]]=n1[i];
    }
    }
    for1(i,1,n){
    if (n2[i]>n2[i-1]){
        m2[n2[i]]=m2[n2[i-1]]+1;
        ry[m2[n2[i]]]=n2[i];
    }
    }
    for1(i,1,n){
    if (n3[i]>n3[i-1]){
        m3[n3[i]]=m3[n3[i-1]]+1;
        rz[m3[n3[i]]]=n3[i];
    }
    }
    for1(i,1,n){
    a[i].x=m1[a[i].x];
    a[i].y=m2[a[i].y];
    a[i].z=m3[a[i].z];
    }
}
struct IT{
vector<int>st;
void resz(int _n){
st.resize(4*_n+9);
}
void rep(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)/2;
rep(id*2,l,mid,u,val);
rep(id*2+1,mid+1,r,u,val);
st[id]=max(st[id*2],st[id*2+1]);
}
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    st[id]=max(st[id],val);
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int walk(int id,int l,int r,int val){
//max suffix >=val
if (l==r&&st[id]>val)return l;
if (st[id]<=val)return -1;
int mid=(l+r)/2;
if (st[id*2+1]>val){
    return walk(id*2+1,mid+1,r,val);
}
return walk(id*2,l,mid,val);
}
};
int best[maxn];
void yz(){
    IT st1,st2,st3;
    //st1 mean match for z
    //st2 mean max z
    //st3 mean max sum
    st1.resz(n);
    st2.resz(n);
    st3.resz(n);
    multiset<pii>bestpair;
    multiset<pii>::iterator it;
    for1(i,1,n)best[i]=0;
    for1(i,1,n){
    int p=i;
    for1(j,i,n){
    if (a[i].x==a[j].x){
        p=j;
    }
    else break;
    }
    for1(j,i,p){
    int checkpoint=st2.walk(1,1,n,a[j].z);
    if (checkpoint>a[j].y){
        ans=max(ans,rx[a[j].x]+st3.get(1,1,n,a[j].y+1,checkpoint));
    }
    }
    for1(j,i,p){
    int vl=st1.get(1,1,n,1,a[j].y-1);
    if (vl>a[j].z){
        //have pair {a[i].y,a[i].z}
        //if (j==9)cerr<<a[j].y<<" "<<vl<<'\n';
        if (best[a[j].y]==0){
            //cerr<<j<<'\n';
            pii tmp={a[j].y,vl};
            bool canadd=true;
            if (!bestpair.empty()){
            while (!bestpair.empty()){//check for a[j].y<a[i].y and a[j].z<a[i].z
                it=bestpair.upper_bound(tmp);
                if (it==bestpair.begin())break;
                it--;
                auto temp=(*it);
                if (temp.se<=tmp.se){
                    bestpair.erase(it);
                    st2.rep(1,1,n,temp.fi,0);
                    st3.rep(1,1,n,temp.fi,0);
                    best[temp.fi]=0;
                }
                else {
                    break;
                }
            }
            if (!bestpair.empty()){
            it=bestpair.upper_bound(tmp);
            if (!bestpair.empty()&&it!=bestpair.end()){
                auto temp=(*it);
                if (temp.se>=tmp.se){
                    canadd=false;
                }
            }
            }
            }
            if (canadd){
                bestpair.insert(tmp);
                best[a[j].y]=vl;
                st2.rep(1,1,n,tmp.fi,tmp.se);
                st3.rep(1,1,n,tmp.fi,ry[tmp.fi]+rz[tmp.se]);
            }
        }
        else if (best[a[j].y]<vl){
            //cerr<<j<<" "<<best[a[<<'\n';
            bestpair.erase(bestpair.find({a[j].y,best[a[j].y]}));
            st2.rep(1,1,n,a[j].y,0);
            st3.rep(1,1,n,a[j].y,0);
            best[a[j].y]=0;
            pii tmp={a[j].y,vl};
            bool canadd=true;
            if (!bestpair.empty()){
            while (!bestpair.empty()){//check for a[j].y<a[i].y and a[j].z<a[i].z
                it=bestpair.upper_bound(tmp);
                if (it==bestpair.begin())break;
                it--;
                auto temp=(*it);
                if (temp.se<=tmp.se){
                    bestpair.erase(it);
                    st2.rep(1,1,n,temp.fi,0);
                    st3.rep(1,1,n,temp.fi,0);
                    best[temp.fi]=0;
                }
                else {
                    break;
                }
            }
            if (!bestpair.empty()){
            it=bestpair.upper_bound(tmp);
            if (!bestpair.empty()&&it!=bestpair.end()){
                auto temp=(*it);
                if (temp.se>=tmp.se){
                    canadd=false;
                }
            }
            }
            }
            if (canadd){
                bestpair.insert(tmp);
                best[a[i].y]=vl;
                st2.rep(1,1,n,tmp.fi,tmp.se);
                st3.rep(1,1,n,tmp.fi,ry[tmp.fi]+rz[tmp.se]);
            }
        }
    }
    st1.update(1,1,n,a[j].y,a[j].z);
    }
    i=p;
    }
    //for (auto v:bestpair)cout<<v.fi<<" "<<v.se<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n;
    for1(i,1,n){
    cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+1+n);
    nenso();
    //for1(i,1,n)cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<'\n';
    yz();
    for1(i,1,n){
    swap(a[i].y,a[i].z);
    swap(ry[i],rz[i]);
    }
    //for1(i,1,n)cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<'\n';
    yz();
    cout<<ans;
}

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