oj.uz

답안 #701022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701022 2023-02-19T19:02:45 Z ParsaS 별자리 3 (JOI20_constellation3) C++17
0 / 100
 7 ms 14420 KB 
// In the name of God
// sorry M
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 2e5 + 5, L = 3;
int n, m, A[N], H[N];
int id[N], sprc[N][L], ver, tin[N], tout[N], T;
int fen[N];
set<pair<int, pair<int, int> > > st[N];
vector<int> adj[N];
ll dp[N];

ll query(int i) {
    ll res = 0;
    for (i; i > 0; i -= i & -i)
        res += fen[i];
    return res;
}
void upd(int i, int val) {
    for (i; i < N; i += i & -i)
        fen[i] += val;
}
void range_upd(int l, int r, int val) {
    upd(l, val);
    upd(r + 1, -val);
}

void _merge(int v, int u) {
    if (st[v].size() < st[u].size())
        st[v].swap(st[u]);
    for (auto x : st[u])
        st[v].insert(x);
}

void dfs(int v, int p = 0) {
    tin[v] = ++T;
    int lc = 0, rc = 0;
    for (auto u : adj[v]) {
        dfs(u, v);
        _merge(v, u);
        if (lc == 0)
            lc = u;
        else
            rc = u;
    }
    if (rc) {
        range_upd(tin[lc], tout[lc], dp[rc]);
        range_upd(tin[rc], tout[rc], dp[lc]);
    }
    dp[v] = dp[lc] + dp[rc];
    range_upd(tin[v], tin[v], dp[v]);
    while (!st[v].empty() && st[v].begin()->fi <= H[p]) {
        dp[v] = max(dp[v], query(tin[st[v].begin()->se.fi]) + st[v].begin()->se.se);
        //cout << "rem " << v << ' ' << st[v].begin()->se.fi << ' ' << query(tin[st[v].begin()->se.fi]) << endl;
        st[v].erase(st[v].begin());
    }
    tout[v] = ++T;
    //cout << v << ' ' << dp[v] << endl;
}

int build(int l, int r) {
    if (r < l)
        return -1;
    int lg = __lg(r - l + 1);
    int v = sprc[l][lg];
    if (A[v] < A[sprc[r - (1 << lg) + 1][lg]])
        v = sprc[r - (1 << lg) + 1][lg];
    id[v] = ++ver;
    int u = ver;
    H[u] = A[v];
    int lc = build(l, v - 1);
    int rc = build(v + 1, r);
    if (lc > -1)
        adj[u].pb(lc);
    if (rc > -1)
        adj[u].pb(rc);
    return u;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = n; i >= 1; i--) {
        sprc[i][0] = i;
        for (int l = 1; l < L; l++) {
            sprc[i][l] = sprc[i][l - 1];
            if (i + (1 << (l - 1)) <= n && A[sprc[i][l]] < A[sprc[i + (1 << (l - 1))][l - 1]])
                sprc[i][l] = sprc[i + (1 << (l - 1))][l - 1];
        }
    }
    build(1, n);
    ll sum = 0;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c; cin >> x >> y >> c;
        st[id[x]].insert(mp(y, mp(id[x], c)));
        sum += c;
    }
    H[0] = 1e9 + 10;
    dfs(1);
    //cout << dp[1] << endl;
    cout << sum - dp[1];
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}

Compilation message

constellation3.cpp: In function 'll query(int)':
constellation3.cpp:20:10: warning: statement has no effect [-Wunused-value]
   20 |     for (i; i > 0; i -= i & -i)
      |          ^
constellation3.cpp: In function 'void upd(int, int)':
constellation3.cpp:25:10: warning: statement has no effect [-Wunused-value]
   25 |     for (i; i < N; i += i & -i)
      |          ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -