제출 #973728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973728		Ooops_sorry	별자리 3 (JOI20_constellation3)	C++14	0 / 100	13 ms	34396 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 (l > r) return N - 1;
  if (l == r) {
    for (auto p : mas[l]) {
      sets[l].insert(p.first);
      update_pos(1, 0, N - 1, p.first, p.second);
    }
    return l;
  }
  int m = tr.get(l, r).second;
  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);
  }
  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 best2 = max(0ll, get(1, 0, N - 1, 0, a[m]));
  ll cur_mx = 0, best1 = 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; 
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'long long int solve(long long int, long long int)':
constellation3.cpp:154:21: 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]
  154 |   for (int i = 0; i < lol.size(); i++) {
      |                   ~~^~~~~~~~~~~~
constellation3.cpp:162:21: 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]
  162 |   for (int i = 0; i < lol.size(); i++) {
      |                   ~~^~~~~~~~~~~~
constellation3.cpp:163:30: 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]
  163 |     int R = min(a[m], (i + 1 < lol.size() ? lol[i + 1][0] - 1 : N - 1));
      |                        ~~~~~~^~~~~~~~~~~~
constellation3.cpp:174:21: 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]
  174 |   for (int i = 0; i < lol.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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