Submission #1208838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208838		sula2	나일강 (IOI24_nile)	C++20	30 / 100	2095 ms	7136 KiB

nile

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

struct dsu {
    vector<int> par, rank, size;
    int odd_comps = 0;
    
    dsu(int n): par(n), rank(n), size(n, 1), odd_comps(n) {
        iota(all(par), 0);
    }
    
    int find(int u) {
        return par[u] == u ? u : par[u] = find(par[u]);
    }
    
    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u != v) {
            if (rank[u] < rank[v]) swap(u, v);
            par[v] = u;
            rank[u] += rank[u] == rank[v];
            odd_comps -= size[u] & 1;
            odd_comps -= size[v] & 1;
            size[u] += size[v];
            odd_comps += size[u] & 1;
        }
    }
};

vector<long long> sub6(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
        ) {
    int n = W.size(), q = E.size();
    vector<int> E_ind(q);
    iota(all(E_ind), 0);
    sort(all(E_ind), [&](int i, int j) { return E[i] < E[j]; });
    vector<int> W_ind(n);
    iota(all(W_ind), 0);
    sort(all(W_ind), [&](int i, int j) { return W[i] < W[j]; });
    vector<pair<int,int>> edges;
    for (int i = 0; i < n-1; i++)
        edges.emplace_back(W_ind[i+1] - W_ind[i], i);
    sort(all(edges));
    int ptr = 0;
    dsu d(n);
    vector<long long> ans(q);
    for (int i : E_ind) {
        while (edges[ptr].first <= E[i]) {
            d.merge(edges[ptr].second, edges[ptr].second + 1);
        }
        ans[i] = 2*d.odd_comps;
    }
    return ans;
}

struct segtree {
    vector<long long> tree;
    int offset = 1;

    segtree(int n) {
        while (offset < n) offset <<= 1;
        tree.resize(offset << 1);
    }

    void update(int i, long long x) {
        tree[i += offset] = x;
        while (i >>= 1) tree[i] = min(tree[i*2], tree[i*2 + 1]);
    }

    long long query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 1e18;
        int mid = l+r >> 1;
        return min(query(2*v, l, mid, ql, qr),
            query(2*v+1, mid+1, r, ql, qr));
    }

    long long query(int l, int r) { return query(1, 0, offset - 1, l, r); }
};

long long solve(vector<int> W, vector<int> A,
                vector<int> B, int D) {
    int n = W.size();
    vector<int> ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&](int i, int j) { return W[i] < W[j]; });
    vector<long long> dp(n);
    segtree s(n);
    dp[0] = A[ind[0]];
    long long sum = A[ind[0]];
    int j = 0;
    s.update(0, -A[ind[0]] + B[ind[0]]);
    for (int i = 1; i < n; i++) {
        while (W[ind[i]] - W[ind[j]] > D)
            j++;
        dp[i] = dp[i-1] + A[ind[i]];
        if (j < i) {
            dp[i] = min(dp[i], sum + s.query(j, i-1) + B[ind[i]]);
        }
        sum += A[ind[i]];
        s.update(i, -sum + dp[i-1] + B[ind[i]]);
    }
    return dp[n-1];
}

vector<long long> calculate_costs(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
        ) {
    bool subtask6 = true;
    for (int x : A) subtask6 &= x == 2;
    for (int x : B) subtask6 &= x == 1;
    if (subtask6) {
        return sub6(W, A, B, E);
    }
    int n = W.size(), q = E.size();
    vector<long long> res(q);
    for (int i = 0; i < q; i++) {
        res[i] = solve(W, A, B, E[i]);
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 11 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18