Submission #1097351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097351		thangdz2k7	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	288 ms	93268 KiB

constellation3

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, a[N], root;
ii rmq[N][LG];
vi adj[N];

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

void getEd(int p, int l, int r){
    if (l > r) return;
    int u = get(l, r).se;
    if (!p) root = u; else adj[p].pb(u);
    getEd(u, l, u - 1); getEd(u, u + 1, r);
}

int timer, t_in[N], t_out[N], jump[N][LG];

void dfs1(int u = root){
    t_in[u] = ++ timer;
    for (int j = 1; j < LG; ++ j){
        int to = jump[u][j - 1];
        if (!to) break;
        jump[u][j] = jump[to][j - 1];
    }
    for (int v : adj[u]) {
        jump[v][0] = u; dfs1(v);
    }
    t_out[u] = timer;
}

vector <ii> stars[N];
ll dp[N], bit[N];

void upd(int l, int r, ll v){
    for (; l <= n; l += l & -l) bit[l] += v;
    for (r = r + 1; r <= n; r += r & -r) bit[r] -= v;
}

ll qry(int u){
    ll ans = 0;
    for (; u; u -= u & -u) ans += bit[u];
    return ans;
}

void dfs2(int u = root){
    int s = 0;
    for (int v : adj[u]) dfs2(v), s += v, dp[u] += dp[v];
    for (int v : adj[u]) if (v ^ s) upd(t_in[v], t_out[v], dp[s - v]);

    for (auto [x, c] : stars[u]){
        ll cost = c;
        cost += qry(t_in[x]);
        for (int v : adj[x]) cost += dp[v];
        maxl(dp[u], cost);
    }
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i]; rmq[i][0] = {a[i], i};
    }

    for (int i = n; i >= 1; -- i){
        for (int j = 1; j < LG; ++ j){
            int u = i + (1 << (j - 1));
            if (u > n) break;
            rmq[i][j] = max(rmq[i][j - 1], rmq[u][j - 1]);
        }
    }
    getEd(0, 1, n); dfs1();

    int m; cin >> m; ll ans = 0;
    while (m --){
        int x, y, c; cin >> x >> y >> c; ans += c;
        int u = x; for (int j = LG - 1; j >= 0; -- j){
            int to = jump[u][j];
            if (to && a[to] < y) u = to;
        }
        stars[u].pb({x, c});
    }
    dfs2();

    cout << ans - dp[root];
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

constellation3.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
constellation3.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
constellation3.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
constellation3.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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