Submission #991779

#	Time	Username	Problem	Language	Result	Execution time	Memory
991779		snpmrnhlol	Team Contest (JOI22_team)	C++17	100 / 100	261 ms	19028 KiB

team

#include<bits/stdc++.h>
using namespace std;
const int N = 15e4;
const int inf = 2e9;
struct xyz{
    int x,y,z;
}v[N];
int p[N];
int pos[N];
int n;
int ans = -1;
set <int> instances;
set <int> good;
struct nod{
    int mxy,mxz;
}seg[4*N];
nod operator+(nod a,nod b){
    return {max(a.mxy,b.mxy),max(a.mxz,b.mxz)};
}
void upd(int pos, int y, int z, int l = 0, int r = n - 1, int node = 1){
    if(l == r){
        seg[node].mxy = y;
        seg[node].mxz = z;
    }else{
        int mij = (l + r)/2;
        if(pos <= mij){
            upd(pos, y, z, l, mij, node*2);
        }else{
            upd(pos, y, z, mij + 1, r, node*2 + 1);
        }
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
}
nod get2(int ql,int qr,int l = 0,int r = n - 1,int node = 1){
    //cout<<seg[node].mxy<<' '<<seg[node].mxz<<' '<<ql<<' '<<qr<<' '<<l<<' '<<r<<' '<<node<<"????\n";
    if(ql <= l && r <= qr){
        return seg[node];
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            return get2(ql,qr,l,mij,node*2);
        }else if(mij + 1 <= ql){
            return get2(ql,qr,mij + 1,r,node*2 + 1);
        }else{
            return get2(ql,qr,l,mij,node*2) + get2(ql,qr,mij + 1,r,node*2 + 1);
        }
    }
}
void del(int x){
    int id = pos[x];
    if(instances.find(id) != instances.end()){
        upd(id, -inf, -inf);
        instances.erase(id);
    }
}
nod get(){
    while(!instances.empty()){
        auto id = *instances.rbegin();
        nod x = get2(0,id);
        if(x.mxy > v[p[id]].y || x.mxz > v[p[id]].z)break;
        instances.erase(prev(instances.end()));
    }
    if(instances.empty())return {-inf,-inf};
    nod p = get2(0,*instances.rbegin());
    return p;
}
int main(){
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>v[i].x>>v[i].y>>v[i].z;
        p[i] = i;
    }
    sort(v,v + n,[&](xyz a,xyz b){
         return a.x < b.x;
    });
    sort(p,p + n,[&](int a,int b){
         if(v[a].y == v[b].y)return v[a].z < v[b].z;
         return v[a].y < v[b].y;
    });
    for(int i = 0;i < n;i++){
        //cout<<v[p[i]].y<<' '<<v[p[i]].z<<'\n';
        pos[p[i]] = i;
        instances.insert(i);
        upd(i, v[p[i]].y, v[p[i]].z);
    }
    int pt = n - 1;
    for(int i = n - 1;i >= 0;i--){
        while(pt >= 0 && v[pt].x >= v[i].x){
            del(pt);
            pt--;
        }
        nod f = get();
        if(f.mxy > v[i].y && f.mxz > v[i].z){
            ans = max(ans,f.mxy + f.mxz + v[i].x);
        }
    }
    cout<<ans;
    return 0;
}

• 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