Submission #545304

#	Time	Username	Problem	Language	Result	Execution time	Memory
545304		leaked	Team Contest (JOI22_team)	C++14	100 / 100	613 ms	23556 KiB

team

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const ll inf=1e18;
const int N=160'000+1;
int mx[4*N],mn[4*N];
void upd(int i,int x,int v,int tl,int tr){
    if(tl==tr){
        umax(mx[v],x);umin(mn[v],x);
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=i)
        upd(i,x,2*v,tl,tm);
    else
        upd(i,x,2*v+1,tm+1,tr);
    mx[v]=max(mx[v<<1],mx[v<<1|1]);
    mn[v]=min(mn[v<<1],mn[v<<1|1]);
}
int getmax(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r) return mx[v];
    if(tl>r||tr<l) return -1e9;
    int tm=(tl+tr)>>1;
    return max(getmax(l,r,v<<1,tl,tm),getmax(l,r,v<<1|1,tm+1,tr));
}
int getmin(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r) return mn[v];
    if(tl>r||tr<l) return 1e9;
    int tm=(tl+tr)>>1;
    return min(getmin(l,r,v<<1,tl,tm),getmin(l,r,v<<1|1,tm+1,tr));
}
signed main(){
    fast_resp;
    int n;
    cin>>n;
    vec<vec<int>>a(n,vec<int>(3));
    vec<vec<int>> kek(3);
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
            kek[j].pb(a[i][j]);
        }
    }
    for(int j=0;j<3;j++){
        sort(all(kek[j]));
        kek[j].erase(unique(all(kek[j])),kek[j].end());
    }
    vec<vec<int>> ids(n,vec<int>());
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++)
            a[i][j]=lower_bound(all(kek[j]),a[i][j])-kek[j].begin();
        ids[a[i][0]].pb(i);
    }
    int mxt=-1;
    fill(mx,mx+4*N,-1e9);fill(mn,mn+4*N,1e9);
    int m=sz(kek[1]);
    int j=-1;
    for(int x=0;x<n;x++){
        for(auto &i : ids[x]){
            if(j<=a[i][1]) continue;
//            cout<<"WO "<<j<<' '<<a[i][1]<<' '<<getmax(0,j,1,0,endl;
            if(getmax(0,j-1,1,0,m-1)>max(getmin(j,m-1,1,0,m-1),a[i][2])){
                umax(mxt,kek[0][a[i][0]]+kek[1][j]+kek[2][getmax(0,j-1,1,0,m-1)]);
            }
        }
        for(auto &i : ids[x]){
//            cout<<"ADD "<<a[i][1]<<' '<<a[i][2]<<endl;
            upd(a[i][1],a[i][2],1,0,m-1);
        }
//        if(kek[0][x]==4){
//            x=x;
//            cout<<"W "<<endl;
//        }
        for(auto &i : ids[x]){
            /// suppose i'm in prefmax
            int l=a[i][1]+1,r=m;
            while(l!=r){
                int tm=(l+r)>>1;
                if(getmin(tm,m-1,1,0,m-1)<a[i][2]) l=tm+1;
                else r=tm;
            }
            --l;
            if(l!=a[i][1]) umax(j,l);
            ///i'ma sufmin
            if(getmax(0,a[i][1]-1,1,0,m-1)>a[i][2]){
                umax(j,a[i][1]);
            }
        }
    }
    cout<<mxt;
    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