Submission #376272

#	Time	Username	Problem	Language	Result	Execution time	Memory
376272		valerikk	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	310 ms	23032 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = (int)2e5 + 7;

ll f[N];

void add(int pos, ll delt) {
  for (int i = pos + 1; i < N; i += i & -i) f[i] += delt;
}

void addseg(int l, int r, ll delt) {
  add(l, delt);
  add(r, -delt);
}

ll get(int pos) {
  ll sum = 0;
  for (int i = pos; i > 0; i -= i & -i) sum += f[i];
  return sum;
}

int n, a[N];
int m;
int x[N], y[N];
ll c[N];
int l[N], r[N];
vector<int> who[N];
int ord[N];

bool cmp(int i, int j) {
  return make_pair(r[i] - l[i], make_pair(l[i], i)) < make_pair(r[j] - l[j], make_pair(l[j], j));
}

signed main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
  }
  cin >> m;
  for (int i = 0; i < m; ++i) {
    cin >> x[i] >> y[i] >> c[i];
    --x[i];
    --y[i];
    who[x[i]].push_back(i);
  }
  vector<pair<int, int>> st = {{(int)1e9, -1}};
  for (int i = 0; i < n; ++i) {
    while (!st.empty() && st.back().first <= a[i]) st.pop_back();
    st.push_back({a[i], i});
    for (int ind : who[i]) l[ind] = lower_bound(st.rbegin(), st.rend(), make_pair(y[ind], -1))->second + 1;
  }
  st = {{(int)1e9, n}};
  for (int i = n - 1; i >= 0; --i) {
    while (!st.empty() && st.back().first <= a[i]) st.pop_back();
    st.push_back({a[i], i});
    for (int ind : who[i]) r[ind] = lower_bound(st.rbegin(), st.rend(), make_pair(y[ind], -1))->second;
  }
  for (int i = 0; i < m; ++i) ord[i] = i;
  sort(ord, ord + m, cmp);
  ll sum = 0;
  for (int i = 0; i < m; ++i) sum += c[i];
  for (int i = 0; i < m; ++i) {
    int ind = ord[i];
    ll curr = c[ind] - get(x[ind] + 1);
    if (curr > 0) {
      sum -= curr;
      addseg(l[ind], r[ind], curr);
    }
  }
  cout << sum << endl;
  return 0;
}

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