oj.uz

답안 #213027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213027 2020-03-24T18:56:04 Z dolphingarlic 별자리 3 (JOI20_constellation3) C++14
0 / 100
 13 ms 14464 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m;
ll ans = 0;

ll segtree[800001], lazy[800001];

void push_lazy(int node, int l, int r) {
    segtree[node] += lazy[node];
    if (l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int a, int b, ll val, int node = 1, int l = 1, int r = n) {
    push_lazy(node, l, r);
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
        lazy[node] = val;
        push_lazy(node, l, r);
    } else {
        int mid = (l + r) / 2;
        update(a, b, val, node * 2, l, mid);
        update(a, b, val, node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

ll query(int a, int b, int node = 1, int l = 1, int r = n) {
    push_lazy(node, l, r);
    if (l > b || r < a) return 0;
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return max(query(a, b, node * 2, l, mid), query(a, b, node * 2 + 1, mid + 1, r));
}

int cmp[200001];
pair<int, int> range[200001];

int find(int A) {
    while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}

void onion(int A, int B) {
    A = find(A), B = find(B);
    range[A].first = min(range[A].first, range[B].first);
    range[A].second = min(range[A].second, range[B].second);
    cmp[B] = A;
}

bool active[200001];

int a[200001];
vector<int> cmp_start[200002];
vector<pair<int, ll>> col[200001], row[200001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> a[i];
        cmp_start[a[i] + 1].push_back(i);
    }
    cin >> m;
    FOR(i, 1, m + 1) {
        int x, y;
        ll v;
        cin >> x >> y >> v;
        col[x].push_back({y, v});
        ans += v;
    }

    FOR(i, 1, n + 1) {
        sort(col[i].begin(), col[i].end());
        vector<pair<int, ll>> keep;
        ll last = 0;
        for (pair<int, ll> j : col[i]) if (j.second > last) {
            keep.push_back(j);
            last = j.second;
        }
        last = 0;
        for (pair<int, ll> j : keep) {
            row[j.first].push_back({i, j.second - last});
            last = j.second;
        }
    }

    iota(cmp + 1, cmp + n + 1, 1);
    FOR(i, 1, n + 1) range[i] = {i, i};

    FOR(i, 1, n + 1) {
        for (int x : cmp_start[i]) {
            ll l_mx = 0, r_mx = 0, dp = 0;

            if (x - 1 && active[x - 1]) {
                l_mx = query(range[find(x - 1)].first, range[find(x - 1)].second);
                dp += l_mx;
            }
            if (x + 1 <= n && active[x + 1]) {
                r_mx = query(range[find(x + 1)].first, range[find(x + 1)].second);
                dp += r_mx;
            }

            if (x - 1 && active[x - 1])
                update(range[find(x - 1)].first, range[find(x - 1)].second, r_mx);
            if (x + 1 <= n && active[x + 1])
                update(range[find(x + 1)].first, range[find(x + 1)].second, l_mx);

            if (x - 1 && active[x - 1]) onion(x - 1, x);
            if (x + 1 <= n && active[x + 1]) onion(x, x + 1);
            active[x] = true;
            update(x, x, dp);
        }
        
        for (pair<int, ll> star : row[i]) update(star.first, star.first, star.second);
    }

    ll mx = 0;
    FOR(i, 1, n + 1) {
        if (a[i] == n) {
            ans -= mx;
            mx = 0;
        } else mx = max(mx, query(i, i));
    }
    ans -= mx;
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 65.0

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