oj.uz

Submission #1028306

# Submission time Handle Problem Language Result Execution time Memory
1028306 2024-07-19T16:18:08 Z DennisTran Constellation 3 (JOI20_constellation3) C++17
0 / 100
 4 ms 10076 KB 
#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) {
    long long sum = 0;
    for (int v : ke[u]) {
        DFS(v);
        sum += dp[v];
    }

    tree1.update(tin[u], tout[u], sum);
    dp[u] = sum;
    for (auto x : stars[u]) {
        dp[u] = max(dp[u], x.second + tree1.get(tin[x.first]) - tree2.get(tin[p[0][x.first]]) + dp[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];
        cnode = p[0][cnode];
        stars[cnode].emplace_back(x, c);
    }

    DFS(root);
    cout << Total - dp[root];
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message

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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 10076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 10076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 10076 KB Output isn't correct
2 Halted 0 ms 0 KB -