제출 #488552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488552		boris_mihov	Sum Zero (RMI20_sumzero)	C++14	0 / 100	13 ms	19628 KiB

sumzero

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

int sparse[maxlog][maxn];
int jump[maxn], 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);

    }

}

int search(int l, int r) {

    // cout << "search: " << l << ' ' << r << ' ' << in_chain[l] << ' ' << chain[in_chain[l]][0] << ' ' << pos_chain[l] << ' ' << parent[chain[in_chain[l]][0]] << '\n';
    if (chain[in_chain[l]][0] < r) return search(parent[chain[in_chain[l]][0]], r) + pos_chain[l]+1;

    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';
    return pos_chain[l] - rbinary;

}

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

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

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

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

    }

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

    }

    // for (int i = 1 ; i <= n ; ++i)
    //     cout << jump[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;
        cout << search(l, r) << '\n';

    }


}

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