Submission #1244017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244017		m5588ohammed	Team Contest (JOI22_team)	C++20	0 / 100	2095 ms	30920 KiB

team

#include <bits/stdc++.h>
#define endl "\n"
#define mod 1000000007
using namespace std;
#define int long long
const int N=(1<<19);
int Tree[N*2+5][2];
int n,inf=3e10;
array <int,6> arr[150001],Marr[150001];
int cnt=0;
void update(int i,int val,int u){
    i+=N;
    Tree[i][u]=max(Tree[i][u],val);
    i/=2;
    while(i!=0){
        Tree[i][u]=max(Tree[i*2][u],Tree[i*2+1][u]);
        i/=2;
    }
    return;
}

int solve(int l1,int r1,int i,int l,int r,int u){
    if(l1>r||l>r1) return -inf;
    if(l<=l1&&r1<=r) return Tree[i][u];
    return max(solve(l1,(l1+r1)/2,i*2,l,r,u),solve((l1+r1)/2+1,r1,i*2+1,l,r,u));
}
void compress(){
    set <int> comp;
    map <int,int> key;
    for(int i=1;i<=n;i++){
        comp.insert(arr[i][0]);
        comp.insert(arr[i][1]);
        comp.insert(arr[i][2]);
    }
    for(int i:comp){
        key[i]=++cnt;
    }
    for(int i=1;i<=n;i++) for(int u=0;u<=2;u++) arr[i][u]=key[arr[i][u]];
    return;
}
int calc(){
    for(int i=0;i<=N*2+4;i++) Tree[i][0]=Tree[i][1]=-inf;
    for(int i=1;i<=n;i++) arr[i]=Marr[i];
    compress();
    sort(arr+1,arr+n+1);
    // for(int i=1;i<=n;i++) cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[i][2]<<endl;
    // exit(0);
    int mx=-1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(arr[i][1]<=arr[j][1]) continue;
            int val=solve(0,N-1,1,0,arr[i][1]-1,0);
            if(val<=max(arr[i][5],arr[j][5])) continue;
            mx=max(mx,arr[j][3]+arr[i][4]+val);
        }
        for(int j=i+1;j<=n;j++){
            if(arr[i][2]<=arr[j][2]) continue;
            int val=solve(0,N-1,1,0,arr[i][2]-1,1);
            if(val<=max(arr[i][4],arr[j][4])) continue;
            mx=max(mx,arr[j][3]+arr[i][5]+val);
        }
        update(arr[i][1],arr[i][5],0);
        update(arr[i][2],arr[i][4],1);
    }
    return mx;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>Marr[i][0]>>Marr[i][1]>>Marr[i][2];
        Marr[i][3]=Marr[i][0];
        Marr[i][4]=Marr[i][1];
        Marr[i][5]=Marr[i][2];
    }
    cout<<calc()<<endl;
}

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