Submission #1244135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244135		erering	Team Contest (JOI22_team)	C++20	18 / 100	2092 ms	37996 KiB

team

#include <bits/stdc++.h>
#define pb push_back
//#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5,inf=2e8,MOD=1e9+9;
struct node{
    node* l=NULL;
    node* r=NULL;
    node* seg=NULL;
    int mx=-inf;
};
node* root=new node;
node* root2=new node;
node* rooty=new node;
node* rootz=new node;
int offset=1;
const int MXV=4000+5;
int flag2=0;
void update(node* cur,int idx,int lo,int hi,int val){
    if(lo>idx || hi<idx)return;
    if(lo==idx && hi==idx){
        cur->mx=max(cur->mx,val);
        return;
    }
    int mid=(lo+hi)/2;
    if(cur->l==NULL)cur->l=new node;
    if(cur->r==NULL)cur->r=new node;
    update(cur->l,idx,lo,mid,val);
    update(cur->r,idx,mid+1,hi,val);
    cur->mx=max({cur->mx,cur->l->mx,cur->r->mx});
}
int query2(node* cur,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return cur->mx;
    if(lo>qhi || hi<qlo)return -inf;
    int mx=-inf,mid=(lo+hi)/2;
    if(cur->l!=NULL)mx=max(mx,query2(cur->l,qlo,qhi,lo,mid));
    if(cur->r!=NULL)mx=max(mx,query2(cur->r,qlo,qhi,mid+1,hi));
    return mx;
}
int query(node* cur,int qlo,int qhi,int lo,int hi,int z){
    if(lo>=qlo && hi<=qhi){
        if(cur->seg==NULL)return -inf;
        return query2(cur->seg,z+1,MXV,0,offset-1);
    }
    if(lo>qhi || hi<qlo)return -inf;
    if(cur->l==NULL)cur->l=new node;
    if(cur->r==NULL)cur->r=new node;
    int mx=-inf,mid=(lo+hi)/2;
    if(cur->l!=NULL)mx=max(mx,query(cur->l,qlo,qhi,lo,mid,z));
    if(cur->r!=NULL)mx=max(mx,query(cur->r,qlo,qhi,mid+1,hi,z));
    return mx;
}
int uglytask;
void insert(node* cur,int idx,int lo,int hi,int val){
    if(lo>idx || hi<idx)return;
    if(lo==idx && hi==idx){
        if(cur->seg==NULL)cur->seg=new node;
        int z;
        if(!flag2)z=query(rooty,0,idx-1,0,offset-1,val);
        else if(flag2==1)z=query(rootz,0,idx-1,0,offset-1,val);
        else{
            uglytask=-1;
            update(cur->seg,val,0,offset-1,val);
            return;
        }
        uglytask=z;
        update(cur->seg,z,0,offset-1,idx+z);
        return;
    }
    int mid=(lo+hi)/2;
    if(cur->l==NULL)cur->l=new node;
    if(cur->r==NULL)cur->r=new node;
    insert(cur->l,idx,lo,mid,val);
    insert(cur->r,idx,mid+1,hi,val);
    int a=-inf,b=-inf;
    if(cur->seg==NULL)cur->seg=new node;
    if(uglytask!=-1)val=uglytask;
    int v=query2(cur->seg,val,val,0,offset-1);
    if(idx>=lo && idx<=mid){
        a=query2(cur->l->seg,val,val,0,offset-1);
    }
    else b=query2(cur->r->seg,val,val,0,offset-1);
    update(cur->seg,val,0,offset-1,max({v,a,b}));
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin>>n;
    while(offset<MXV)offset*=2;
    int ans=-1;
    pair<int,pair<int,int>> p[n];
    for(int i=0;i<n;i++){
        int x,y,z; cin>>x>>y>>z;
        p[i]={x,{y,z}};
        int sol;
        sol=query(root,y+1,MXV-5,0,offset-1,z);
        sol=max(sol,query(root2,z+1,MXV-5,0,offset-1,y));
        sol+=x;
        ans=max(ans,sol);
    }
    sort(p,p+n);
    for(int i=0;i<n;i++){
        int x=p[i].first,y,z;
        if(i>0 && x!=p[i-1].first){
            for(int j=i-1;j>=0;j--){
                if(j!=i-1 && p[j].first!=p[j+1].first)break;
                y=p[j].second.first; z=p[j].second.second;
                flag2=0;
                insert(root,y,0,offset-1,z);
                flag2=1;
                insert(root2,z,0,offset-1,y);
                flag2=2;
                insert(rooty,y,0,offset-1,z);
                insert(rootz,z,0,offset-1,y);
            }
        }
        y=p[i].second.first; z=p[i].second.second;
        int sol;
        sol=query(root,y+1,MXV-5,0,offset-1,z);
        sol=max(sol,query(root2,z+1,MXV-5,0,offset-1,y));
        sol+=x;
        ans=max(ans,sol);
    }
    cout<<ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27