Submission #1166066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166066		Zero_OP	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	280 ms	67912 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r) - 1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define sum_of(v) accumulate(all(v), 0ll)
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vl = vector<ll>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 2e5 + 5;

namespace FenwickTree{
      ll bit[MAX]; int n;
      void update(int id, ll val){
            for(; id <= n; id += id & (-id)) bit[id] += val;
      }

      ll query(int id){
            ll sum = 0;
            for(; id > 0; id -= id & (-id)) sum += bit[id];
            return sum;
      }

      ll query(int l, int r){
            return query(r) - query(l-1);
      }
}

int N, M, A[MAX], l[MAX], r[MAX], up[20][MAX], tin[MAX], tout[MAX], timer_dfs;
pi rmq[20][MAX];
vpi path[MAX];
ll dp[MAX], sum_dp[MAX];

pi query_max(int l, int r){
      int k = 31 - __builtin_clz(r - l + 1);
      return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int initCatersianTree(int L, int R){
      int m = query_max(L, R).ss;
      if(L<m) up[0][l[m] = initCatersianTree(L, m-1)] = m;
      if(m<R) up[0][r[m] = initCatersianTree(m+1, R)] = m;
      return m;
}

void dfs(int u){
//      cout << dbg(u) << '\n';
      tin[u] = ++timer_dfs;
      if(l[u] != -1) dfs(l[u]);
      if(r[u] != -1) dfs(r[u]);
      tout[u] = timer_dfs;
}

bool inside(int u, int v){
      return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int find_subtree(int u, int c){
      if(l[u] != -1 && inside(l[u], c)) return l[u];
      if(r[u] != -1 && inside(r[u], c)) return r[u];
      return -1;
}

void update(int u, ll val){
      FenwickTree::update(tin[u], +val);
      FenwickTree::update(tout[u]+1, -val);
}

ll sum_path(int u, int v){
      return FenwickTree::query(tin[v]) - FenwickTree::query(tin[u]);
}

void calc(int u){
      if(l[u] != -1){
            calc(l[u]);
            sum_dp[u] += dp[l[u]];
      }

      if(r[u] != -1){
            calc(r[u]);
            sum_dp[u] += dp[r[u]];
      }

      maximize(dp[u], sum_dp[u]);

      update(u, sum_dp[u]);
      for(auto [v, c] : path[u]){
            maximize(dp[u], sum_path(u, v) + sum_dp[u] + c);
      }
      update(u, -dp[u]);
}

int main(){
      setIO();

      cin >> N;
      FOR(i, 0, N) {
            cin >> A[i], rmq[0][i] = mp(A[i], i);
            l[i] = -1; r[i] = -1;
      }

      for(int i = 1; (1 << i) <= N; ++i){
            FOR(j, 0, N - (1 << i) + 1) rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]);
      }

      memset(up, -1, sizeof(up));
      int rt = initCatersianTree(0, N-1);
      dfs(rt);

//      FOR(i, 0, N) cout << up[0][i] << " \n"[i == N-1];

      for(int i = 1; (1 << i) < N; ++i){
            FOR(j, 0, N){
                  if(up[i-1][j] == -1) up[i][j] = -1;
                  else up[i][j] = up[i-1][up[i-1][j]];
            }
      }

      cin >> M;
      ll sum = 0;
      FOR(i, 0, M){
            int X, Y, C;
            cin >> X >> Y >> C;
            --X;

            sum += C;

            int pos = X;
            for(int i = 31 - __builtin_clz(N-1); i >= 0; --i){
                  if(up[i][pos] != -1 && A[up[i][pos]] < Y) pos = up[i][pos];
            }

            path[pos].eb(X, C);
      }


      FenwickTree::n = timer_dfs;
      calc(rt);
      cout << sum - dp[rt] << '\n';

      return 0;
}

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