Submission #488561

#	Time	Username	Problem	Language	Result	Execution time	Memory
488561		boris_mihov	Sum Zero (RMI20_sumzero)	C++14	0 / 100	12 ms	19568 KiB

sumzero

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
const int maxn = 4e5+10;

int parent[maxn];
vector < int > v[maxn];
vector < int > chain[maxn];
int in_chain[maxn], pos_chain[maxn];
int a[maxn], n, q;
int subtree[maxn], nextc[maxn];

void init_subtree(int x) {

    int which = 0;
    for (int i : v[x]) {

        init_subtree(i);
        subtree[x] += subtree[i];
        if (subtree[i] >= subtree[which]) which = i;

    }

    ++subtree[x];
    nextc[x] = which;

}

int cnt = 1;
void build_chain(int x) {

    in_chain[x] = cnt;
    pos_chain[x] = chain[cnt].size();
    chain[cnt].push_back(x);
    if (nextc[x] != 0) build_chain(nextc[x]);

    for (int i : v[x]) {

        if (i == nextc[x]) continue;
        
        ++cnt;
        build_chain(i);

    }

}

void search(int l, int r) {

    int ans = 0;
    while (parent[chain[in_chain[l]][0]] <= r+1) {
        
        // cout << "search: " << l << ' ' << r << ' ' << in_chain[l] << ' ' << chain[in_chain[l]][0] << ' ' << parent[chain[in_chain[l]][0]] << ' ' << pos_chain[l] << ' ' << parent[chain[in_chain[l]][0]] << '\n';
        ans += pos_chain[l]+1;
        l = parent[chain[in_chain[l]][0]];

    }

    // cout << "search: " << ans << ' ' << l << ' ' << r << ' ' << in_chain[l] << ' ' << chain[in_chain[l]][0] << ' ' << parent[chain[in_chain[l]][0]] << ' ' << pos_chain[l] << ' ' << parent[chain[in_chain[l]][0]] << '\n';

    int lbinary = -1, rbinary = chain[in_chain[l]].size(), mid;
    while (lbinary < rbinary - 1) {

        mid = (lbinary + rbinary) / 2;
        if (chain[in_chain[l]][mid] > r+1) lbinary = mid;
        else rbinary = mid; 

    }

    // cout << "found: " << rbinary << ' ' << chain[in_chain[l]][rbinary] << '\n';
    cout << pos_chain[l] - rbinary + ans << '\n';

}

unordered_map < long long, int > um;
void solve() {

    parent[n+2] = maxn;

    fill(parent, parent+n+3, n+2);

    long long sum = 0;
    for (int i = 1 ; i <= n+1 ; ++i) {

        parent[um[sum]] = i;
        um[sum] = i;
        sum += a[i];

    }

    for (int i = n+1 ; i >= 1 ; --i) {
        
        parent[i] = min(parent[i], parent[i+1]);
        v[parent[i]].push_back(i);

    }

    for (int i = 1 ; i <= n ; ++i)
        for (int j : v[i])
            parent[j] = i;

    // for (int i = 1 ; i <= n ; ++i)
    //     cout << parent[i] << ' ';
    // cout << '\n';

    init_subtree(n+2);
    build_chain(n+2);

    // cout << "tree: \n";
    // for (int i = 1 ; i <= n+2 ; ++i)
    //     for (int j : v[i])
    //         cout << i << ' ' << j << '\n';

    cout << "chains: \n";
    for (int i = 1 ; i <= cnt ; ++i, cout << '\n')
        for (int j : chain[i])
            cout << j << ' ';

    int l, r;
    cin >> q;

    for (int i = 1 ; i <= q ; ++i) {

        cin >> l >> r;
        search(l, r);

    }


}

void fast_io() {

    ios_base :: sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

}

void read() {

    cin >> n;
    for (int i = 1 ; i <= n ; ++i)
        cin >> a[i];

}

int main () {

    fast_io();
    read();
    solve();

    return 0;
    
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39