Submission #1177161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177161		zNatsumi	Team Contest (JOI22_team)	C++20	0 / 100	55 ms	18688 KiB

team

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n;
struct info{
  int x, y, z;
  info(): x(0), y(0), z(0) {}
  info(int x, int y, int z): x(x), y(y), z(z) {}
} a[N];
int lim, pre_y[N], pre_z[N];
vector<int> rrh;

void init(){
  for(int i = 1; i <= n; i++){
    rrh.push_back(a[i].y);
    rrh.push_back(a[i].z);
  }
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());
  for(int i = 1; i <= n; i++){
    a[i].y = lower_bound(rrh.begin(), rrh.end(), a[i].y) - rrh.begin() + 1;
    a[i].z = lower_bound(rrh.begin(), rrh.end(), a[i].z) - rrh.begin() + 1;
  }
  lim = rrh.size();
}

struct BIT2D{
  vector<int> node[N], bit[N];

  void fake_update(int x, int y){
    for(int i = x; i > 0; i -= i & -i) node[i].push_back(y);
  }
  void fake_get(int x, int y){
    for(int i = x; i <= lim; i += i & -i) node[i].push_back(y);
  }
  void init(){
    for(int i = 1; i <= lim; i++){
      auto &a = node[i];
      sort(a.begin(), a.end());
      a.erase(unique(a.begin(), a.end()), a.end());
      bit[i].resize(a.size(), -1);
    }
  }
  void update(int x, int y, int val){
    for(int i = x; i > 0; i -= i & -i)
      for(int j = lower_bound(node[i].begin(), node[i].end(), y) - node[i].begin() + 1; j > 0; j -= j & -j){
        bit[i][j - 1] = max(bit[i][j - 1], val);
      }
  }
  int get(int x, int y){
    int res = -1;
    for(int i = x; i <= lim; i += i & -i)
      for(int j = lower_bound(node[i].begin(), node[i].end(), y) - node[i].begin() + 1; j <= node[i].size(); j += j & -j){
        res = max(res, bit[i][j - 1]);
      }
    return res;
  }
} fwk2d;

struct BIT{
  int bit[N];
  void build(){
    memset(bit, -1, sizeof bit);
  }
  void update(int i, int x){
    for(; i <= lim; i += i & -i) bit[i] = max(bit[i], x);
  }
  int get(int i){
    int res = -1;
    for(; i > 0; i -= i & -i) res = max(res, bit[i]);
    return res;
  }
} fwk1, fwk2;

void fakeSolve(){
  int ptl = 1;
  fwk1.build();
  fwk2.build();
  for(int i = 1; i <= n; i++){
    fwk2d.fake_get(a[i].y, a[i].z);

    if(i < n && a[i].x < a[i + 1].x){
      while(ptl <= i){
        int _z = fwk1.get(a[ptl].y - 1); pre_z[ptl] = _z;
        int _y = fwk2.get(a[ptl].z - 1); pre_y[ptl] = _y;

        if(_z != -1 && _z > a[ptl].z) fwk2d.fake_update(a[ptl].y, _z);
        if(_y != -1 && _y > a[ptl].z) fwk2d.fake_update(_y, a[ptl].z);
        fwk1.update(a[ptl].y, a[ptl].z);
        fwk2.update(a[ptl].z, a[ptl].y);

        ptl += 1;
      }
    }
  }
  fwk2d.init();
}

void Solve(){
  int ptl = 1, res = -1;
  for(int i = 1; i <= n; i++){
    int tmp = fwk2d.get(a[i].y, a[i].z);
    if(tmp != -1) res = max(res, a[i].x + tmp);

    if(i < n && a[i].x < a[i + 1].x){
      while(ptl <= i){
        int _z = pre_z[ptl];
        int _y = pre_y[ptl];

        if(_z != -1 && _z > a[ptl].z) fwk2d.update(a[ptl].y, _z, rrh[a[ptl].y - 1] + rrh[_z - 1]);
        if(_y != -1 && _y > a[ptl].z) fwk2d.update(_y, a[ptl].z, rrh[_y - 1] + rrh[a[ptl].z - 1]);
        ptl += 1;
      }
    }
  }
  cout << res << "\n";
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++){
    int x, y, z; cin >> x >> y >> z;
    a[i] = {x, y, z};
  }
  sort(a + 1, a + n + 1, [&](info a, info b){ return a.x < b.x; });

  init();
  fakeSolve();
  Solve();
}

• 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