Submission #1243976

#TimeUsernameProblemLanguageResultExecution timeMemory
1243976emad234Team Contest (JOI22_team)C++20
0 / 100
46 ms2120 KiB
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
bool operator<(pii a,pii b){
  return make_pair(a.F,-1 * a.S) < make_pair(b.F,-1 * b.S);
}
struct node{
  node *l,*r;
  pii val;
  node(): l(NULL), r(NULL), val({0,0}){}
};
node *root1 = new node(),*root2 = new node();
pii query(int l,int r,int s,int e,node *cur){
  if(l > e || r < s) return {0,0};
  if(l >= s && r <= e) return cur->val;
  pii op1 = {0,0},op2 = {0,0};
  int md = (l + r) / 2;
  if(cur->l) op1 = query(l,md,s,e,cur->l);
  if(cur->r) op2 = query(md + 1,r,s,e,cur->r);
  return max(op1,op2);
}
void update(int l,int r,int ind,pii val,node *cur){
  if(l == r){
    cur->val = max(cur->val,val);
    return;
  }
  int md = (l + r) / 2;
  if(!cur->l) cur->l = new node();
  if(!cur->r) cur->r = new node();
  if(ind <= md) {
    update(l,md,ind,val,cur->l);
  }
  else {
    update(md + 1,r,ind,val,cur->r);
  }
  cur->val = max(cur->l->val,cur->r->val);
}
struct player{
  int x,y,z;
  friend bool operator<(player a, player b){
    return a.x < b.x;
  }
};
player a[mxN];
signed main(){
  int n;
  cin >>n;
  int N;
  for(int i = 1;i <= n;i++){
    cin >>a[i].x>> a[i].y>> a[i].z;
    N = max({a[i].x,a[i].y,a[i].z,N});
  }
  N = exp2(ceil(log2(N)));
  sort(a + 1,a + n + 1);
  int ans = -1;
  int prev = 0;
  queue<pii>buff;
  for(int i = 1;i <= n;i++){
    // cout<<"TES\n";
    // if(a[i].x != prev){
    //   while(buff.size()){
    //
    //   }
    // }
    pii x = query(1,N,1,a[i].y - 1,root1);
    update(1,N,a[i].y,{a[i].z,a[i].y},root1);
    pii y = query(1,N,a[i].y + 1,N,root2);
    // cout<<"{ "<<x.F<<' '<<x.S<<" } , { "<<y.F<<' '<<y.S<<" }\n";
    if(y.S){
      ans = max(ans,a[i].x + y.F);
    }
    if(x.S) update(1,N,a[i].y,{x.F + a[i].y,a[i].y},root2);
  }
  cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...