oj.uz

Submission #991695

# Submission time Handle Problem Language Result Execution time Memory
991695 2024-06-02T19:48:43 Z snpmrnhlol Team Contest (JOI22_team) C++17
0 / 100
 1 ms 2480 KB 
#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;
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];
    upd(id, -inf, -inf);
    instances.erase(id);
}
int get(){
    int l = 0,r = n - 1;
    while(l != r){
        int mij = (l + r + 1)/2;
        int x = *instances.lower_bound(mij);
        nod y = get2(0,mij);
        //cout<<0<<' '<<mij<<' '<<y.mxy<<' '<<y.mxz<<'\n';
        if(y.mxy <= v[p[x]].y && y.mxz <= v[p[x]].z){
            //cout<<l<<' '<<r<<' '<<v[p[x]].y<<' '<<v[p[x]].z<<' '<<y.mxy<<' '<<y.mxz<<"asdf\n";
            r = mij - 1;
        }else l = mij;
    }
    //for(auto i:instances)cout<<i<<' ';cout<<'\n';
    //cout<<0<<' '<<l<<'\n';
    nod p = get2(0,l);
    if(p.mxy == -inf)return -inf;
    return p.mxy + p.mxz;
}
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++){
        pos[p[i]] = i;
        instances.insert(i);
        upd(i, v[p[i]].y, v[p[i]].z);
        //cout<<v[p[i]].y<<' '<<v[p[i]].z<<'\n';
    }
    int pt = n - 1;
    for(int i = n - 1;i >= 0;i--){
        while(pt >= 0 && v[pt].x >= v[i].x){
            del(pt);
            pt--;
        }
        ans = max(ans,get() + v[i].x);
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2480 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2480 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2480 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -