Submission #999461

#	Time	Username	Problem	Language	Result	Execution time	Memory
999461		abczz	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	642 ms	142020 KiB

constellation3

#include <iostream>
#include <array>
#include <vector>
#define ll long long

using namespace std;

vector <array<ll, 2>> V[200002];
vector <ll> H[200002];
vector <ll> U;
array<ll, 2> R[200002][2];
vector <ll> adj[200002][2];
ll n, m, l, r, mid, f, s, z, mx, opt, cnt, A[200002], bl[200002][19], br[200002][19], x, y, c;

struct SegTree_MAX{
  ll st[800008];
  void update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      st[id] = max(st[id], w);
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}ST;
struct SegTree_ADD{
  ll st[800008], lazy[800008];
  void push(ll id) {
    st[id*2] += lazy[id];
    lazy[id*2] += lazy[id];
    st[id*2+1] += lazy[id];
    lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
  }
  void update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st[id] += w;
      lazy[id] += w;
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    update(id*2, l, mid, ql, qr, w);
    update(id*2+1, mid+1, r, ql, qr, w);
  }
  ll query(ll id, ll l, ll r, ll q) {
    if (l == r) return st[id];
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) return query(id*2, l, mid, q);
    else return query(id*2+1, mid+1, r, q);
  }
}tree[2];

void dfs(ll id, ll u) {
  R[u][id][0] = cnt;
  for (auto v : adj[u][id]) {
    dfs(id, v);
  }
  R[u][id][1] = cnt++;
}

int main() {
  cin >> n;
  A[0] = 1e18;
  for (int i=1; i<=n; ++i) {
    cin >> A[i];
    if (A[i] > mx) {
      mx = A[i];
      z = i;
    }
    --A[i];
  }
  A[n+1] = 1e18;
  cin >> m;
  for (int i=0; i<m; ++i) {
    cin >> x >> y >> c;
    --y;
    f += c;
    V[y].push_back({x, c});
  }
  V[n].push_back({z, 0});
  for (int i=0; i<=n+1; ++i) {
    while (!U.empty() && A[U.back()] < A[i]) U.pop_back();
    if (U.empty()) bl[i][0] = i;
    else bl[i][0] = U.back();
    U.push_back(i);
    if (i != bl[i][0]) adj[bl[i][0]][0].push_back(i);
  }
  U.clear();
  for (int i=n+1; i>=0; --i) {
    while (!U.empty() && A[U.back()] < A[i]) U.pop_back();
    if (U.empty()) br[i][0] = i;
    else br[i][0] = U.back();
    U.push_back(i);
    if (i != br[i][0]) adj[br[i][0]][1].push_back(i);
  }
  dfs(0, 0);
  cnt = 0;
  dfs(1, n+1);
  for (int i=1; i<=n; ++i) {
    H[A[i]].push_back(i);
  }
  for (int i=0; i<=n; ++i) {
    for (auto [x, w] : V[i]) {
      s = tree[0].query(1, 0, n+1, R[x][0][1]) + tree[1].query(1, 0, n+1, R[x][1][1]) + w;
      //cout << "? " << R[x][1][1] << " " << tree[1].query(1, 0, n+1, R[x][1][1]) << endl;
      //cout << x << " " << i+1 << " " << s << " " << tree[0].query(1, 0, n+1, R[x][0][1]) << " " << tree[1].query(1, 0, n+1, R[x][1][1]) << endl;
      opt = max(opt, s);
      ST.update(1, 0, n+1, x, s);
    }
    for (auto u : H[i]) {
      s = ST.query(1, 0, n+1, bl[u][0], u);
      //cout << i << " " << bl[u][0] << " " << u << " " << s << endl;
      tree[0].update(1, 0, n+1, R[u][0][0], R[u][0][1], s);
      z = ST.query(1, 0, n+1, u, br[u][0]);
      //cout << u << " " << R[u][1][0] << " " << R[u][1][1] << " " << z << endl;
      //cout << i << " " << u << " " << br[u][0] << " " << z << endl;
      tree[1].update(1, 0, n+1, R[u][1][0], R[u][1][1], z);
      //cout << u << " " << bl[u][0] << " " << br[u][0] << " " << s << " " << z << endl;
      //cout << u << " " << s << " " << z << endl;
      //opt = max(opt, s+z);
    }
    int j = 0;
    for (auto u : H[i]) {
      s = ST.query(1, 0, n+1, bl[u][0], u);
      z = ST.query(1, 0, n+1, u, br[u][0]);
      ST.update(1, 0, n+1, u, s+z);
    }
  }
  cout << f-opt << '\n';
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:133:9: warning: unused variable 'j' [-Wunused-variable]
  133 |     int j = 0;
      |         ^

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