제출 #1244177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244177		emad234	Team Contest (JOI22_team)	C++20	37 / 100	2095 ms	5984 KiB

team

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const ll mxN = 3e5 + 5;
const ll mod = 1e9 + 7;
using namespace std;
struct node{
  node *l,*r;
  pii val;
  node(): l(NULL), r(NULL), val({0,0}){}
};
node *root1 = new node(),*root2 = new node();
pii query(ll l,ll r,ll s,ll 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};
  ll 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(ll l,ll r,ll ind,pii val,node *cur){
  if(l == r){
    cur->val = max(cur->val,val);
    return;
  }
  ll 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{
  ll x,y,z;
  friend bool operator<(player a, player b){
    return tie(a.x,a.y,a.z) < tie(b.x,b.y,b.z);
  }
};
struct upd{
  ll ind;
  pii val;
  node *cur;
};
player a[mxN];
signed main(){
  ll n;
  cin >>n;
  ll N;
  for(ll 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 = (1LL << 32);
  sort(a + 1,a + n + 1);
  ll ans = -1;
  ll prev = 0;
  queue<upd>buff;
  for(ll i = 1;i <= n;i++){
    // cout<<"TES\n";
    if(a[i].x != prev){
      while(buff.size()){
        auto u = buff.front();
        buff.pop();
        update(1,N,u.ind,u.val,u.cur);
      }
      prev = a[i].x;
    }
    for(int j = 1;j < i;j++){
      if(a[i].x == a[j].x || a[i].y >= a[j].y) continue;
      pii x = query(1,N,1,a[j].y - 1,root1);
      if(x.S && x.F > a[i].z && x.F > a[j].z) ans = max(ans,a[i].x + a[j].y + x.F);
    }
    // pii x = query(1,N,1,a[i].y - 1,root1);
    // pii y = query(1,N,a[i].y + 1,N,root2);
    // pii z = query(1,N,1,a[i].y,root1);
    // cout<<"{ "<<x.F<<' '<<x.S<<" } , { "<<y.F<<' '<<y.S<<" }\n";
    // if(y.S && y.F - y.S > a[i].z) ans = max({ans,a[i].x + y.F});
    // if(y.S && y.F - y.S > a[i].z && z.F > y.F - y.S && z.F > a[i].z) ans = max({ans,a[i].x + y.S + z.F});
    buff.push({a[i].y,{a[i].z,a[i].y},root1});
    // update(1,N,a[i].y,{a[i].z,a[i].y},root1);
  }
  cout<<ans;
}

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