Submission #213326

#	Time	Username	Problem	Language	Result	Execution time	Memory
213326		IOrtroiii	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	361 ms	72952 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200200;
const int LG = 18;
using ll = long long;

int N, M;
int A[MAXN];
int rmq[LG][MAXN];

int best(int x, int y) {
   if (A[x] > A[y]) return x;
   else return y;
}

ll ans[MAXN], offset[MAXN];
multiset<pair<int, ll>> vals[MAXN];

int get(int l, int r) {
   int lg = __lg(r - l + 1);
   return best(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]);
}

int solve(int l, int r, int lim) {
   int v;
   if (l == r) {
      v = l;
   } else {
      int md = get(l, r);
      v = solve(md, md, A[md]);
      if (l < md) {
         int u = solve(l, md - 1, A[md]);
         if (vals[v].size() < vals[u].size()) {
            swap(v, u);
         }
         for (auto z : vals[u]) {
            vals[v].emplace(z.first, z.second + ans[v] - ans[u]);
         }
         offset[v] += offset[u] + ans[u];
      }
      if (md < r) {
         int u = solve(md + 1, r, A[md]);
         if (vals[v].size() < vals[u].size()) {
            swap(v, u);
         }
         for (auto z : vals[u]) {
            vals[v].emplace(z.first, z.second + ans[v] - ans[u]);
         }
         offset[v] += offset[u] + ans[u];
      }
   }
   while (!vals[v].empty() && vals[v].begin()->first <= lim) {
      ans[v] = max(ans[v], vals[v].begin()->second);
      vals[v].erase(vals[v].begin());
   }
   return v;
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   cin >> N;
   for (int i = 0; i < N; ++i) {
      cin >> A[i];
      rmq[0][i] = i;
   }
   for (int i = 1; i < LG; ++i) {
      for (int j = 0; j + (1 << i) <= N; ++j) {
         rmq[i][j] = best(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
      }
   }
   cin >> M;
   ll sum = 0;
   while (M--) {
      int x, y; ll c;
      cin >> x >> y >> c;
      vals[--x].emplace(y, c);
      sum += c;
   }
   int v = solve(0, N - 1, N + 1);
   cout << sum - (ans[v] + offset[v]) << "\n";
   return 0;
}

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