Submission #1125759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125759		VinhLuu	Team Contest (JOI22_team)	C++20	100 / 100	1559 ms	46236 KiB

team

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int oo = -1e9;

int n, a[N], b[N], c[N];
vector<int> rrh, rz, px;

struct ST{
  int m;
  struct node {
    int mx[2], last[2], kq[2], we[2];
  } st[N << 2];

  void build(int i,int l,int r) {
    if(l == r) {
      for(int j = 0; j <= 1; j ++) {
        st[i].mx[j] = oo;
        st[i].last[j] = -1;
        st[i].kq[j] = oo;
        st[i].we[j] = -1;
      }
      return;
    }
    int mid = (l + r) / 2;
    build(i << 1, l, mid);
    build(i << 1|1, mid + 1, r);
    for(int j = 0; j <= 1; j ++) {
      st[i].mx[j] = oo;
      st[i].last[j] = -1;
      st[i].kq[j] = oo;
      st[i].we[j] = -1;
    }
  }

  void collect(int& fi, int& tfi, int& se, int& tse,int val,int x) {
    if(x == tfi && tfi != -1) fi = max(fi, val);
    else if(x == tse && tse != -1) se = max(se, val);
    else {
      if(fi < val) {
        se = fi, tse = tfi;
        fi = val;
        tfi = x;
      } else if(se < val) {
        se = val;
        tse = x;
      }
    }
  }

  void add(int i,int l,int r,int u,int val,int x) {
    if(l > r || r < u || u < l) return;
    if(l == r) {
      collect(st[i].mx[0], st[i].last[0], st[i].mx[1], st[i].last[1], val, x);
      return;
    }
    int mid = (l + r) / 2;
    add(i << 1, l, mid, u, val, x);
    add(i << 1|1, mid + 1, r, u, val, x);
    collect(st[i].mx[0], st[i].last[0], st[i].mx[1], st[i].last[1], val, x);
  }

  int ret[2], t[2];

  void get(int i,int l,int r,int u,int v,int val,int x) {
    if(l > r || r < u || v < l) return;
    if(u <= l && r <= v) {
      if(st[i].last[0] > x && st[i].last[0] != -1) collect(ret[0], t[0], ret[1], t[1], st[i].mx[0] + val, st[i].last[0]);
      if(st[i].last[1] > x && st[i].last[1] != -1) collect(ret[0], t[0], ret[1], t[1], st[i].mx[1] + val, st[i].last[1]);
      return;
    }
    int mid = (l + r) / 2;
    get(i << 1, l, mid, u, v, val, x);
    get(i << 1|1, mid + 1, r, u, v, val, x);
  }

  tuple<int,int,int,int> pre(int pos,int val,int x) {
    ret[0] = ret[1] = oo;
    t[0] = t[1] = oo;
    get(1, 1, m, 1, pos - 1, val, x);
    return {ret[0], t[0], ret[1], t[1]};
  }

  void update(int i,int l,int r,int u,int fi,int tfi,int se,int tse) {
    if(l > r || r < u || u < l) return;
    if(l == r) {
      collect(st[i].kq[0], st[i].we[0], st[i].kq[1], st[i].we[1], fi, tfi);
      collect(st[i].kq[0], st[i].we[0], st[i].kq[1], st[i].we[1], se, tse);
      return;
    }
    int mid = (l + r) / 2;
    update(i << 1, l, mid, u, fi, tfi, se, tse);
    update(i << 1|1, mid + 1, r, u, fi, tfi, se, tse);
    collect(st[i].kq[0], st[i].we[0], st[i].kq[1], st[i].we[1], fi, tfi);
    collect(st[i].kq[0], st[i].we[0], st[i].kq[1], st[i].we[1], se, tse);
  }

  void query(int i,int l,int r,int u,int v,int val,int x) {
    if(l > r || r < u || v < l) return;
    if(u <= l && r <= v) {
      if(st[i].we[0] > x && st[i].we[0] != -1) collect(ret[0], t[0], ret[1], t[1], st[i].kq[0] + val, st[i].we[0]);
      if(st[i].we[1] > x && st[i].we[1] != -1) collect(ret[0], t[0], ret[1], t[1], st[i].kq[1] + val, st[i].we[1]);
      return;
    }
    int mid = (l + r) / 2;
    query(i << 1, l, mid, u, v, val, x);
    query(i << 1|1, mid + 1, r, u, v, val, x);
  }

  int pick(int pos,int val,int x) {
    ret[0] = ret[1] = oo;
    t[0] = t[1] = oo;
    query(1, 1, m, pos + 1, m, val, x);
    return max(ret[0], ret[1]);
  }

} Y, Z;

// 0 -> 0 0
// 1 -> 1 0
// 2 -> 0 1
// 3 -> 1 1

int ans = -1;

vector<int> Q[N];

void solve() {
  px.clear();
  rrh.clear();
  rz.clear();

  for(int i = 1; i <= n; i ++) {
    px.push_back(a[i]);
    rrh.push_back(b[i]);
    rz.push_back(c[i]);
  }
  sort(all(px)); px.resize(unique(all(px)) - px.begin());
  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
  sort(all(rz)); rz.resize(unique(all(rz)) - rz.begin());
  for(int i = 1; i <= n; i ++) {
    int tmp = pot(px, a[i]);
    Q[tmp].push_back(i);
  }

  int Max = oo;

  Y.m = (int)rrh.size();
  Z.m = (int)rz.size();

  Y.build(1, 1, Y.m);
  Z.build(1, 1, Z.m);

  for(int k = 1; k <= (int)px.size(); k ++) {
    for(auto j : Q[k]) {
      int pos_b = pot(rrh, b[j]);
      int pos_c = pot(rz, c[j]);
      int val = oo;
      val = Y.pick(pos_b, a[j], c[j]);
      if(val != oo) ans = max(ans, val);
      val = Z.pick(pos_c, a[j], b[j]);
      if(val != oo) ans = max(ans, val);

    }
    // update add
    for(auto j : Q[k]) {
      int pos_b = pot(rrh, b[j]);
      int pos_c = pot(rz, c[j]);
      auto tmp = Y.pre(pos_b, b[j], c[j]);
      int x, y, z, t; tie(x, y, z, t) = tmp;
      if(x != oo) Y.update(1, 1, Y.m, pos_b, x, y, z, t);
      tmp = Z.pre(pos_c, c[j], b[j]);
      tie(x, y, z, t) = tmp;
      if(x != oo) Z.update(1, 1, Z.m, pos_c, x, y, z, t);

      Y.add(1, 1, Y.m, pos_b, c[j], c[j]);
      Z.add(1, 1, Z.m, pos_c, b[j], b[j]);
    }
    Q[k].clear();
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n;
  for(int i = 1; i <= n; i ++) {
    cin >> a[i] >> b[i] >> c[i];
  }

  solve();
  for(int i = 1; i <= n; i ++) swap(a[i], b[i]);
  solve();
  for(int i = 1; i <= n; i ++) swap(a[i], c[i]);
  solve();
  cout << ans;

}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:193:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
team.cpp:194:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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