oj.uz

Submission #791119

# Submission time Handle Problem Language Result Execution time Memory
791119 2023-07-23T12:32:31 Z winter0101 Team Contest (JOI22_team) C++14
9 / 100
 125 ms 22380 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 (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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 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 0 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 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 0 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 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 96 ms 10912 KB Output is correct
12 Correct 53 ms 7892 KB Output is correct
13 Correct 51 ms 9716 KB Output is correct
14 Correct 81 ms 11740 KB Output is correct
15 Correct 77 ms 11824 KB Output is correct
16 Correct 57 ms 11784 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 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 96 ms 10912 KB Output is correct
12 Correct 53 ms 7892 KB Output is correct
13 Correct 51 ms 9716 KB Output is correct
14 Correct 81 ms 11740 KB Output is correct
15 Correct 77 ms 11824 KB Output is correct
16 Correct 57 ms 11784 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 125 ms 12052 KB Output is correct
23 Runtime error 104 ms 22380 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 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 96 ms 10912 KB Output is correct
12 Correct 53 ms 7892 KB Output is correct
13 Correct 51 ms 9716 KB Output is correct
14 Correct 81 ms 11740 KB Output is correct
15 Correct 77 ms 11824 KB Output is correct
16 Correct 57 ms 11784 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 125 ms 12052 KB Output is correct
23 Runtime error 104 ms 22380 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 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 96 ms 10912 KB Output is correct
12 Correct 53 ms 7892 KB Output is correct
13 Correct 51 ms 9716 KB Output is correct
14 Correct 81 ms 11740 KB Output is correct
15 Correct 77 ms 11824 KB Output is correct
16 Correct 57 ms 11784 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 125 ms 12052 KB Output is correct
23 Runtime error 104 ms 22380 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 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 0 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 -