Submission #973760

#	Time	Username	Problem	Language	Result	Execution time	Memory
973760		Ooops_sorry	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	1394 ms	96020 KiB

constellation3

#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
 
using namespace std;
 
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double 
#define int long long 

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

struct SegTree {
  vector<pair<int, int>> t;
  int n;
  SegTree(int n_) {
    n = 1;
    while (n < n_) {
      n *= 2;
    }
    t.resize(2 * n);
  }
  void upd(int i, pair<int, int> val) {
    i += n;
    t[i] = val;
    for (; i > 1; i /= 2) {
      t[i / 2] = max(t[i], t[i ^ 1]);
    } 
  }
  pair<int, int> get(int l, int r) {
    l += n, r += n + 1;
    pair<int, int> ans{-1, -1};
    while (l < r) {
      if (l & 1) {
        ans = max(ans, t[l++]);
      }
      if (r & 1) {
        ans = max(ans, t[--r]);
      }
      l /= 2, r /= 2;
    }
    return ans;
  }
};

const ll super_inf = 1e18;
const int N = 2e5 + 10;
vector<pair<int, ll>> mas[N];
int a[N];
SegTree tr(N);

ll t[4 * N], add[4 * N];

void inc(int v, ll val) {
  t[v] += val;
  add[v] += val;
}

void push(int v) {
  inc(v * 2, add[v]);
  inc(v * 2 + 1, add[v]);
  add[v] = 0;
}

void update_pos(int v, int l, int r, int pos, ll val) {
  if (l == r) {
    if (val == -super_inf) {
      t[v] = val;
    } else {
      t[v] = max(t[v], val);
    }
    return;
  }
  push(v);
  int m = (l + r) / 2;
  if (pos <= m) {
    update_pos(2 * v, l, m, pos, val);
  } else {
    update_pos(2 * v + 1, m + 1, r, pos, val);
  }
  t[v] = max(t[v * 2], t[v * 2 + 1]);
}

void update(int v, int tl, int tr, int l, int r, ll val) {
  if (l > r) return;
  if (tl == l && tr == r) {
    inc(v, val);
    return;
  }
  push(v);
  int tm = (tl + tr) / 2;
  update(2 * v, tl, tm, l, min(r, tm), val);
  update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
  t[v] = max(t[v * 2], t[v * 2 + 1]);
}

ll get(int v, int tl, int tr, int l, int r) {
  if (l > r) return -super_inf;
  if (tl == l && tr == r) {
    return t[v];
  }
  push(v);
  int tm = (tl + tr) / 2;
  return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}

int pr[N];
set<int> sets[N];

int solve(int l, int r) {
  if (pr[r + 1] - pr[l] == 0) return N - 1;
  int m = tr.get(l, r).second;
  if (mas[m].size() == pr[r + 1] - pr[l]) {
    for (auto p : mas[m]) {
      sets[l].insert(p.first);
      update_pos(1, 0, N - 1, p.first, p.second);
    }
    return l;
  }
  int sz1 = pr[m] - pr[l], sz2 = pr[r + 1] - pr[m + 1], i, j;
  vector<array<ll, 3>> lol;
  if (sz1 > sz2) {
    j = solve(m + 1, r);
    for (int p : sets[j]) {
      lol.pb({p, get(1, 0, N - 1, p, p), 0});
      update_pos(1, 0, N - 1, p, -super_inf);
    }
    assert(t[1] < 0);
    i = solve(l, m - 1);
  } else {
    j = solve(l, m - 1);
    for (int p : sets[j]) {
      lol.pb({p, get(1, 0, N - 1, p, p), 0});
      update_pos(1, 0, N - 1, p, -super_inf);
    }
    assert(t[1] < 0);
    i = solve(m + 1, r);
  }
  assert(sets[i].size() > 0);
  ll best2 = max(0ll, get(1, 0, N - 1, 0, a[m])), best1 = 0;
  if (j != N - 1) {
    assert(sets[j].size() > 0);
    for (int p : sets[j]) {
      sets[i].insert(p);
    }
    for (int i = 0; i < lol.size(); i++) {
      if (lol[i][0] <= a[m]) {
        lol[i][2] = max(0ll, get(1, 0, N - 1, 0, lol[i][0]));
      }
    }
    ll cur_mx = 0;
    int last = -1;
    for (int i = 0; i < lol.size(); i++) {
      int R = min(a[m], (i + 1 < lol.size() ? lol[i + 1][0] - 1 : N - 1));
      cur_mx = max(cur_mx, lol[i][1]);
      if (lol[i][0] <= a[m]) {
        best1 = max(best1, lol[i][1]);
      }
      assert(last < lol[i][0]);
      update(1, 0, N - 1, lol[i][0], R, cur_mx);
      last = R;
    }
    assert(last < a[m] + 1);
    update(1, 0, N - 1, a[m] + 1, N - 1, best1);
    for (int i = 0; i < lol.size(); i++) {
      if (lol[i][0] <= a[m]) {
        update_pos(1, 0, N - 1, lol[i][0], lol[i][2] + lol[i][1]);
      } else {
        update_pos(1, 0, N - 1, lol[i][0], best2 + lol[i][1]);
      }
    }
  }
  for (auto p : mas[m]) {
    update_pos(1, 0, N - 1, p.first, p.second + best1 + best2);
    sets[i].insert(p.first);
  }
  return i;
}

signed main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 0; i < 4 * N; i++) {
    t[i] = -super_inf;
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    tr.upd(i, {a[i], i});
  }
  int m;
  cin >> m;
  ll sum = 0;
  for (int i = 0; i < m; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--;
    if (y <= a[x]) continue;
    sum += c;
    mas[x].pb({y, c});
  }
  for (int i = 0; i < n; i++) {
    pr[i + 1] = pr[i] + mas[i].size();
  }
  solve(0, n - 1);
  ll mx = get(1, 0, N - 1, 0, N - 1);
  cout << sum - mx << endl;
  return 0; 
}

Compilation message (stderr)

constellation3.cpp: In function 'long long int solve(long long int, long long int)':
constellation3.cpp:125:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  125 |   if (mas[m].size() == pr[r + 1] - pr[l]) {
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
constellation3.cpp:158:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int i = 0; i < lol.size(); i++) {
      |                     ~~^~~~~~~~~~~~
constellation3.cpp:165:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for (int i = 0; i < lol.size(); i++) {
      |                     ~~^~~~~~~~~~~~
constellation3.cpp:166:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |       int R = min(a[m], (i + 1 < lol.size() ? lol[i + 1][0] - 1 : N - 1));
      |                          ~~~~~~^~~~~~~~~~~~
constellation3.cpp:177:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (int i = 0; i < lol.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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