Submission #1028310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028310		DennisTran	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	288 ms	74320 KiB

constellation3

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define __Dennis_Tran___ signed main()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
 
using namespace std;
 
const int maxN = 2e5 + 5;
 
int n, a[maxN];
int p[20][maxN];
int tin[maxN], tout[maxN], timer;
long long dp[maxN];
vector <int> ke[maxN];
vector <pair <int, int>> stars[maxN];
 
struct rmq{
    int f[20][maxN];
    int Max(int x, int y) {return a[x] >= a[y] ? x : y;}
    int get(int l, int r) {
        int k = __lg(r - l + 1);
        return Max(f[k][l], f[k][r - (1 << k) + 1]);
    }
    void build() {
        FOR(i, 1, n) f[0][i] = i;
        for (int i = 1; (1 << i) <= n; i++)
            for (int j = 1; j <= n - (1 << i) + 1; j++)
                f[i][j] = Max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
 
    }
} RMQ;
 
int build_Tree(int l, int r, int parent = 0) {
    if (l > r) return 0;
    int mid = RMQ.get(l, r);
    tin[mid] = ++timer;
    ke[parent].emplace_back(mid);
    p[0][mid] = parent;
    FOR(i, 1, 18) p[i][mid] = p[i - 1][p[i - 1][mid]];
    build_Tree(l, mid - 1, mid);
    build_Tree(mid + 1, r, mid);
    tout[mid] = timer;
    return mid;
}
 
struct BIT{
    long long bit[maxN];
    void update(int x, long long val) {
        for (; x <= n; x += x&-x) bit[x] += val;
    }
    void update(int l, int r, long long val) {
        update(l, val);
        update(r + 1, - val);
    }
 
    long long get(int x) {
        long long ans = 0;
        for (; x; x -= x&-x) ans += bit[x];
        return ans;
    }
} tree1, tree2;
 
void DFS(int u) {
    for (int v : ke[u]) {
        DFS(v);
        dp[u] += dp[v];
    }
 
    tree1.update(tin[u], tout[u], dp[u]); 
    for (auto x : stars[u]) {
        dp[u] = max(dp[u], x.second + tree1.get(tin[x.first]) - tree2.get(tin[x.first]));
    }
    tree2.update(tin[u], tout[u], dp[u]);
}
 
__Dennis_Tran___{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr);
 
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    a[n + 1] = n; ++n;
 
    RMQ.build();
    int root = build_Tree(1, n);
 
    long long Total = 0;
    int m; cin >> m; while (m--) {
        int x, y, c; cin >> x >> y >> c;
        int cnode = x; Total += c;
        FOD(i, 18, 0) if (p[i][cnode] && a[p[i][cnode]] < y)
            cnode = p[i][cnode];
        stars[cnode].emplace_back(x, c);
    }
 
    DFS(root);
    cout << Total - dp[root];
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

constellation3.cpp: In member function 'void rmq::build()':
constellation3.cpp:32:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   32 |                 f[i][j] = Max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
      |                                                               ~~^~~

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