Submission #894939

#	Time	Username	Problem	Language	Result	Execution time	Memory
894939		fanwen	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	324 ms	60572 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);

template <class T> struct Fenwick_Tree {
    vector<T> bit;
    int n;
    Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}

    void clear() { fill(bit.begin(), bit.end(), T(0)); }

    void update(int u, T val) {
        for (; u <= n; u += u & -u) bit[u] += val;
    }

    void update(int l, int r, T val) {
        update(l, val);
        update(r + 1, -val);
    }

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

    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

const int MAX = 2e5 + 5;

int n, m, a[MAX], time_in[MAX], time_out[MAX], anc[MAX][20];
vector <int> adj[MAX];
vector <pair <int, int>> stars[MAX];

long long dp[MAX], sum = 0;

void dfs(int u) {
    static int run = 0;
    for (int i = 1; i < 20; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    time_in[u] = ++run;
    for (int v : adj[u]) {
        dfs(v);
    }
    time_out[u] = run;
}

void _dfs(int u) {
    static Fenwick_Tree <long long> bit(n);
    for (int v : adj[u]) {
        _dfs(v);
        dp[u] += dp[v];
    }

    if((int) adj[u].size() == 2) {
        for (int i = 0; i < 2; ++i) {
            bit.update(time_in[adj[u][i]], time_out[adj[u][i]], dp[adj[u][1 ^ i]]);
        }
    }

    for (pair <int, int> tmp : stars[u]) {
        int v, c; tie(v, c) = tmp;
        long long res = bit.get(time_in[v]) + c;
        for (int x : adj[v]) res += dp[x];
        dp[u] = max(dp[u], res);
    }
}

void you_make_it(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        static stack <int> st;
        int last = -1;
        while(!st.empty() && a[st.top()] < a[i]) {
            last = st.top();
            st.pop();
        }

        if(!st.empty()) anc[i][0] = st.top();
        else anc[i][0] = i;
        if(last != -1) anc[last][0] = i;
        st.push(i);
    }

    int rt = 1;
    for (int i = 1; i <= n; ++i) {
        if(anc[i][0] == i) rt = i;
        else adj[anc[i][0]].push_back(i);
    }

    dfs(rt);
    cin >> m; while(m--) {
        int x, y, c; cin >> x >> y >> c;
        sum += c;
        int u = x;
        for (int i = 19; i >= 0; --i) if(a[anc[u][i]] < y) {
            u = anc[u][i];
        }

        stars[u].emplace_back(x, c);
    }

    _dfs(rt);
    cout << sum - dp[rt];
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("JOI20_constellation3");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

constellation3.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = long long int]':
constellation3.cpp:58:42:   required from here
constellation3.cpp:14:9: warning: 'Fenwick_Tree<long long int>::n' will be initialized after [-Wreorder]
   14 |     int n;
      |         ^
constellation3.cpp:13:15: warning:   'std::vector<long long int, std::allocator<long long int> > Fenwick_Tree<long long int>::bit' [-Wreorder]
   13 |     vector<T> bit;
      |               ^~~
constellation3.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
      |     ^~~~~~~~~~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:123:5: note: in expansion of macro 'file'
  123 |     file("JOI20_constellation3");
      |     ^~~~
constellation3.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:123:5: note: in expansion of macro 'file'
  123 |     file("JOI20_constellation3");
      |     ^~~~

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