oj.uz

Submission #791099

# Submission time Handle Problem Language Result Execution time Memory
791099 2023-07-23T12:12:45 Z winter0101 Team Contest (JOI22_team) C++14
0 / 100
 65 ms 20684 KB 
#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 (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;
                }
            }
            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[i].y]<vl){
            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;
                }
            }
            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);
    //for1(i,1,n)cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<'\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]);
    }
    yz();
    cout<<ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Runtime error 1 ms 596 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Runtime error 1 ms 596 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Runtime error 65 ms 20684 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Runtime error 65 ms 20684 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Runtime error 65 ms 20684 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Runtime error 65 ms 20684 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Runtime error 1 ms 596 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -