Submission #1166773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166773		Sang	Nile (IOI24_nile)	C++20	100 / 100	154 ms	22200 KiB

nile

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, a[N], b[N];
ii w[N];

struct ST{
    int n;
    vector<int> T;

    ST() {};
    ST(int _n){
        n = _n;
        int k = 1;
        while(2 * k <= n) k *= 2;
        T.resize(4 * k, INF);
    }

    void update(int id, int l, int r, int pos, int val){
        if (l == r){
            T[id] = val;
            return;
        }
        int m = (l + r)/2;
        if (pos <= m) update(id*2, l, m, pos, val);
        else update(id*2+1, m+1, r, pos, val);
        T[id] = min(T[id*2], T[id*2+1]);
    }

    int get(int id, int l, int r, int u, int v){
        if (l > v || r < u) return INF;
        if (u <= l && r <= v) return T[id];
        int m = (l + r)/2;
        return min(get(id*2, l, m, u, v), get(id*2+1, m+1, r, u, v));
    }
} odd, even;

struct DSU{
    vi lab, mi, s, L, R;
    int ans = 0;
    DSU(int n) : lab(n), mi(n), s(n), L(n), R(n) {};

    void make_set(int u){
        lab[u] = -1;
        s[u] = a[w[u].se] - b[w[u].se];
        mi[u] = INF;
        L[u] = R[u] = u;
    }

    int Find(int u){
        vi q;
        while (lab[u] > 0){
            q.push_back(u);
            u = lab[u];
        }
        for (int &x : q) lab[x] = u;
        return u;
    }

    int get(int u){
        u = Find(u);
        if ((-lab[u])%2 == 0) return s[u];

        int x = min({a[w[L[u]].se] - b[w[L[u]].se], a[w[R[u]].se] - b[w[R[u]].se], mi[u]});
        if (L[u] & 1) x = min(x, odd.get(1, 1, n, L[u], R[u]));
        else x = min(x, even.get(1, 1, n, L[u], R[u]));
        return s[u] - x;
    }

    void active(int u){
        int v = Find(u);
        ans -= get(v);
        mi[v] = min(mi[v], a[w[u].se] - b[w[u].se]);
        ans += get(v);
    }

    void Union(int u, int v){
        if ((u = Find(u)) == (v = Find(v))) return;
        if (lab[u] < lab[v]) swap(u, v);
        ans -= get(u) + get(v);
        lab[u] += lab[v];
        lab[v] = u;
        mi[u] = min(mi[u], mi[v]);
        s[u] += s[v];
        L[u] = min(L[u], L[v]);
        R[u] = max(R[u], R[v]);
        ans += get(u);
    }
};

vector<int> calculate_costs(vector<int32_t> W, vector<int32_t> A, vector<int32_t> B, vector<int32_t> E){
    n = A.size();
    int s = 0, s2 = 0;
    FOR (i, 1, n){
        w[i] = {W[i-1], i};
        a[i] = A[i-1];
        b[i] = B[i-1];
        s += a[i];
        s2 += b[i];
    }
    odd = even = ST(n);
    sort(w + 1, w + n + 1);
    vector<pii> edges;
    FOR (i, 1, n - 1) edges.pb({w[i+1].fi - w[i].fi, {i, i + 1}});
    FOR (i, 1, n){
        if (i & 1) odd.update(1, 1, n, i, a[w[i].se] - b[w[i].se]);
        else even.update(1, 1, n, i, a[w[i].se] - b[w[i].se]);
    }
    DSU dsu(n + 5);
    FOR (i, 1, n) dsu.make_set(i);
    vector<ii> queries, nodes;
    FOR (i, 1, n){
        if (i == 1) nodes.pb({w[i+1].fi-w[i].fi, i});
        else if (i == n) nodes.pb({w[i].fi - w[i-1].fi, i});
        else
            nodes.pb({w[i+1].fi - w[i-1].fi, i});
    }
    FOR (i, 0, (int)E.size() - 1) queries.pb({E[i], i});
    sort(ALL(queries), greater<ii>());
    sort(ALL(edges), greater<pii>());
    sort(ALL(nodes), greater<ii>());
    vector<int> ans(E.size(), 0);
    while (!queries.empty()){
        while (!edges.empty() && edges.back().fi <= queries.back().fi){
            dsu.Union(edges.back().se.fi, edges.back().se.se);
            edges.pop_back();
        }
        while (!nodes.empty() && nodes.back().fi <= queries.back().fi){
            dsu.active(nodes.back().se);
            nodes.pop_back();
        }
        ans[queries.back().se] = s - dsu.ans;
        queries.pop_back();
    }
    return ans;
}

#ifdef _Pbrngw_

signed main() {
    freopen("2-02.in", "r", stdin);
    string s; cin >> s;
    int32_t N, Q;
    cin >>N;
    vector<int32_t> A(N), B(N), W(N);
    FOR (i, 0, N - 1) cin >> W[i] >> A[i] >> B[i];
    cin >> Q;
    vector<int32_t> E(Q);
    FOR (i, 0, Q - 1) cin >> E[i];
    vi ans = calculate_costs(W, A, B, E);
    //vi ans2 = calculate_costs_slow(W, A, B, E);
    for (int &x : ans) cout << x << '\n';
    //for (int &x : ans2) cout << x << '\n';

    return 0;
}
#endif // _Pbrngw_

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