Submission #994479

#	Time	Username	Problem	Language	Result	Execution time	Memory
994479		abczz	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	626 ms	162704 KiB

worst_reporter2

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#define ll long long
 
using namespace std;
 
struct Node{
  ll chl = -1;
  ll chr = -1;
  ll val = 0;
  ll lazy = 0;
};
vector <Node> st;
vector <ll> U;
ll n, f, cnt, A[200000], H[200000], C[200000], in[200000];
queue <ll> Q;
map <ll, ll> mp;
struct SegTree{
  ll get(ll u) {
    if (u == -1) {
      st.push_back({-1, -1, 0});
      return st.size()-1;
    }
    return u;
  }
  ll rt = -1;
  void init() {
    rt = get(rt);
  }
  void push(ll id) {
    if (st[id].chl != -1) {
      st[st[id].chl].val += st[id].lazy;
      st[st[id].chl].lazy += st[id].lazy;
    }
    if (st[id].chr != -1) {
      st[st[id].chr].val += st[id].lazy;
      st[st[id].chr].lazy += st[id].lazy;
    }
    st[id].lazy = 0;
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) return st[id].val;
    push(id);
    ll mid = (l+r)/2;
    return max(query(st[id].chl, l, mid, ql, qr), query(st[id].chr, mid+1, r, ql, qr));
  }
  void push_up(ll id) {
    st[id].val = max((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  void update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      st[id].val = max(st[id].val, w);
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) {
      st[id].chl = get(st[id].chl);
      update(st[id].chl, l, mid, q, w);
    }
    else {
      st[id].chr = get(st[id].chr);
      update(st[id].chr, mid+1, r, q, w);
    }
    push_up(id);
  }
  ll wa, wb;
  void init_merge(ll i, ll j) {
    wa = wb = 0;
    merge(i, j, 0, mp.size()-1);
  }
  void merge(ll a, ll b, ll l, ll r) {
    push(a);
    push(b);
    ll mid = (l+r)/2, ta, tb;
    //cout << l << " " << r << " " << "R" << " " << wa << " " << wb << endl;
    if (st[a].chr != -1) ta = st[st[a].chr].val;
    if (st[b].chr != -1) tb = st[st[b].chr].val;
    if (st[a].chr != -1 && st[b].chr != -1) {
      merge(st[a].chr, st[b].chr, mid+1, r);
    }
    if (st[a].chr != -1) wa = max(wa, ta);
    if (st[b].chr != -1) wb = max(wb, tb);
    if (st[a].chr == -1 && st[b].chr != -1) {
      st[a].chr = st[b].chr;
      st[st[a].chr].val += wa;
      st[st[a].chr].lazy += wa;
    }
    else if (st[a].chr != -1 && st[b].chr == -1) {
      st[st[a].chr].val += wb;
      st[st[a].chr].lazy += wb;
    }
    if (st[a].chl != -1) ta = st[st[a].chl].val;
    if (st[b].chl != -1) tb = st[st[b].chl].val;
    if (st[a].chl != -1 && st[b].chl != -1) {
      merge(st[a].chl, st[b].chl, l, mid);
    }
    //cout << l << " " << r << " " << "L" << " " << wa << " " << wb << endl;
    //cout << st[a].chl << " " << st[b].chl << " " << st[a].chr << " " << st[b].chr << endl;
    if (st[a].chl != -1) wa = max(wa, ta);
    if (st[b].chl != -1) wb = max(wb, tb);
    if (st[a].chl == -1 && st[b].chl != -1) {
      st[a].chl = st[b].chl;
      st[st[a].chl].val += wa;
      st[st[a].chl].lazy += wa;
    }
    else if (st[a].chl != -1 && st[b].chl == -1) {
      st[st[a].chl].val += wb;
      st[st[a].chl].lazy += wb;
    }
    //cout << st[a].val << " " << st[b].val << " ";
    wa = max(wa, st[a].val);
    wb = max(wb, st[b].val);
    if (l == r) {
      st[a].val = max(st[a].val+wb, st[b].val+wa);
      //cout << st[b].val << "*\n";
    }
    else push_up(a);
    //cout << l << " " << r << " -> " << st[a].val << " " << wa << " " << wb << endl;
  }
}ST[200000];
 
void dfs(ll i, ll id) {
  --in[i];
  U.push_back(i);
  //cout << i+1 << endl;
  /*auto tmp = ST[i].query(ST[i].rt, 0, mp.size()-1, H[i], mp.size()-1);
  ST[i].update(ST[i].rt, 0, mp.size()-1, H[i], tmp+C[i]);
  cout << i+1 << "*" << H[i] << " " << tmp+C[i] << endl;*/
  if (id == -1) id = i;
  else {
    ST[id].init_merge(ST[id].rt, ST[i].rt);
    //cout << ST[id].query(ST[id].rt, 0, mp.size()-1, 0, mp.size()-1) << "*\n";
  }
  if (in[A[i]]) {
    dfs(A[i], id);
  }
}
 
int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i] >> H[i] >> C[i];
    f += C[i];
    --A[i];
    //cout << A[i]+1 << " " << i+1 << endl;
    ++in[A[i]];
    ++mp[H[i]];
    ST[i].init();
  }
  for (auto &[x, y] : mp) {
    y = cnt++;
  }
  for (int i=0; i<n; ++i) {
    H[i] = mp[H[i]];
    if (!in[i]) Q.push(i);
  }
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    //cout << in[u] << endl;
    //cout << A[u]+1 << " " << u+1 << endl;
    auto tmp = ST[u].query(ST[u].rt, 0, mp.size()-1, H[u], mp.size()-1);
    //cout << H[u] << " " << tmp << " " << tmp+C[u] << endl;
    ST[u].update(ST[u].rt, 0, mp.size()-1, H[u], tmp+C[u]);
    --in[A[u]];
    if (!in[A[u]]) Q.push(A[u]);
    ST[A[u]].init_merge(ST[A[u]].rt, ST[u].rt);
    //cout << ST[A[u]].query(ST[A[u]].rt, 0, mp.size()-1, 0, mp.size()-1) << endl;
  }
  ll id = -1;
  for (int i=0; i<n; ++i) {
    if (in[i]) {
      U.clear();
      //cout << i+1 << endl;
      dfs(i, -1);
      //cout << ST[i].query(ST[i].rt, 0, mp.size()-1, 0, mp.size()-1) << endl;
      sort(U.begin(), U.end(), [](auto a, auto b) {
        return H[a] < H[b];
      });
      for (auto u : U) {
        auto tmp = ST[i].query(ST[i].rt, 0, mp.size()-1, H[u], mp.size()-1);
        ST[i].update(ST[i].rt, 0, mp.size()-1, H[u], tmp+C[u]);
        //cout << tmp+C[u] << endl;
        //cout << u+1 << "*" << H[u] << " " << tmp+C[u] << endl;
      }
      f -= ST[i].query(ST[i].rt, 0, mp.size()-1, 0, mp.size()-1);
    }
  }
  cout << f << '\n';
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:175:6: warning: unused variable 'id' [-Wunused-variable]
  175 |   ll id = -1;
      |      ^~
worst_reporter2.cpp: In member function 'void SegTree::merge(long long int, long long int, long long int, long long int)':
worst_reporter2.cpp:79:23: warning: 'ta' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     ll mid = (l+r)/2, ta, tb;
      |                       ^~
worst_reporter2.cpp:79:27: warning: 'tb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     ll mid = (l+r)/2, ta, tb;
      |                           ^~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21