Submission #953832

#	Time	Username	Problem	Language	Result	Execution time	Memory
953832		EJIC_B_KEDAX	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1562 ms	63184 KiB

reconstruction

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef LOCAL
    #pragma GCC optimize("O3")
    // #pragma GCC optimize("Ofast")
    // #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937_64 mt(time(0));

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << fixed << setprecision(30);
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

const int N = 505, M = 100100, K = 350, Q = 1 << 20;
pair<int, pair<int, int>> e[M];
int dsu[N], x[Q];

int get(int a) {
    return dsu[a] == a ? a : dsu[a] = get(dsu[a]);
}

void merge(int a, int b) {
    dsu[get(a)] = get(b);
}

struct segment_tree {
    vector<ll> st;
    int size;
    segment_tree(int sz = Q) {
        size = sz;
        st.resize(2 * sz, 0);
    }
    void add(int l, int r, ll v) {
        l += size;
        r += size;
        while (l <= r) {
            if (l & 1) {
                st[l++] += v;
            }
            if (~r & 1) {
                st[r--] += v;
            }
            l >>= 1;
            r >>= 1;
        }
    }
    ll get(int i) {
        ll res = 0;
        i += size;
        while (i) {
            res += st[i];
            i >>= 1;
        }
        return res;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> e[i].y.x >> e[i].y.y >> e[i].x; e[i].y.x--; e[i].y.y--;
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> x[i];
    }
    sort(e, e + m);
    vector<int> v;
    segment_tree ff, ss;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dsu[j] = j;
        }
        int l = -1, ind = -1;
        v.push_back(i);
        for (int j = v.size() - 1; j >= 0; j--) {
            if (get(e[v[j]].y.x) == get(e[v[j]].y.y)) {
                l = v[j];
                ind = j;
            } else {
                merge(e[v[j]].y.x, e[v[j]].y.y);
            }
        }
        if (ind != -1) {
            v.erase(v.begin() + ind);
        }
        int left = -1, right = q;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (x[mid] >= e[i].x) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (l == -1) {
            ff.add(0, left, e[i].x);
            ss.add(0, left, -1);
        } else {
            int key = e[i].x - ((e[i].x - e[l].x - 1) / 2);
            int r = left;
            left = -1, right = q;
            while (right - left > 1) {
                int mid = (left + right) / 2;
                if (x[mid] >= key) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            ff.add(right, r, e[i].x);
            ss.add(right, r, -1);
        }
    }
    v.clear();
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            dsu[j] = j;
        }
        int l = -1, ind = -1;
        v.push_back(i);
        for (int j = v.size() - 1; j >= 0; j--) {
            if (get(e[v[j]].y.x) == get(e[v[j]].y.y)) {
                l = v[j];
                ind = j;
            } else {
                merge(e[v[j]].y.x, e[v[j]].y.y);
            }
        }
        if (ind != -1) {
            v.erase(v.begin() + ind);
        }
        int left = -1, right = q;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (x[mid] > e[i].x) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (l == -1) {
            ff.add(right, q - 1, -e[i].x);
            ss.add(right, q - 1, 1);
        } else {
            int key = e[i].x + ((e[l].x - e[i].x) / 2);
            int r = right;
            left = -1, right = q;
            while (right - left > 1) {
                int mid = (left + right) / 2;
                if (x[mid] > key) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            ff.add(r, left, -e[i].x);
            ss.add(r, left, 1);
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ff.get(i) + x[i] * ss.get(i) << '\n';
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23