Submission #994477

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cassert>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

struct UnionFind {
    vector<int> ig;
    vector<vector<int>> gi;
    int gn;
    UnionFind(int N) {
        ig.resize(N); gi.resize(N);
        for (int i = 0; i < N; i++) {
            ig[i] = i; gi[i] = {i};
        }
        gn = N;
    }
    void merge(int a, int b) {
        if (same(a, b)) return;
        gn--;
        int x = ig[a], y = ig[b];
        if (gi[x].size() < gi[y].size()) swap(x, y);
        for (int j: gi[y]) {
            ig[j] = x;
        }
        gi[x].insert(gi[x].end(), gi[y].begin(), gi[y].end());
        gi[y].clear();
    }
    bool same(int a, int b) {
        return ig[a] == ig[b];
    }
};


const int MN = 200100;
int n;
ll a[MN], as[MN];

ll calc(ll x) {
    ll mi = as[n-1]-x;
    for (int i = n-2; i >= 2; i--) {
        mi = min(mi, 2*as[i]-mi);
    }
    return a[0]-mi+as[1];
}

int main() {
    ios::sync_with_stdio(0);
    cout << setprecision(20);

    cin >> n;
    for (int i = 0; i < n-1; i++) {
        cin >> a[i];
    }
    as[0] = 0;
    for (int i = 0; i < n-1; i++) {
        as[i+1] = as[i]+a[i];
    }

    map<int, int> mp;
    int m;
    cin >> m;
    UnionFind uf(m);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        int y = as[n-1]-x;
        if (mp.count(y)) {
            uf.merge(i, mp[y]);
        } else {
            mp[y] = i;
        }
    }

    for (int i = n-2; i >= 2; i--) {
        while (true) {
            assert(mp.size());
            auto it = mp.end(); it--;
            auto p = *it;
            if (p.first <= as[i]) break;
            int np = 2*as[i]-p.first;
            mp.erase(it);
            if (mp.count(np)) {
//                cout << "M " << p.second << " " << mp[np] << endl;
                uf.merge(p.second, mp[np]);
            } else {
                mp[np] = p.second;
            }
        }
    }

    int res[MN];
    for (auto p: mp) {
//        cout << p.first << " " << p.second << endl;
        for (int d: uf.gi[uf.ig[p.second]]) {
            res[d] = a[0] - p.first + as[1];
        }
    }

    for (int i = 0; i < m; i++) {
        cout << res[i] << endl;
    }
/*    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cout << calc(x) << endl;
    }*/
    return 0;
}

Submission Info

Judge Result