Submission #646668

#	Time	Username	Problem	Language	Result	Execution time	Memory
646668		Vanilla	Sum Zero (RMI20_sumzero)	C++17	61 / 100	621 ms	24772 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 4e5 + 5;
const int lg = 10;
unordered_map <int64, int> ps;
vector <int> jump [lg];
 
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    ps[0] = 0;
    int n;
    cin >> n;
    int64 s = 0, a = 0;
    for (int i = 0; i < lg; i++) jump[i].push_back(0);
    for (int i = 1; i <= n; i++) jump[0].push_back(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a;
        s+=a;
        if (ps.count(s)) {
            jump[0][ps[s] + 1] = i;
        }
        ps[s] = i;
    }
    for (int i = n - 1; i >= 1; i--){
        jump[0][i] = min(jump[0][i], jump[0][i + 1]);
    }
    for (int k = 1; k < lg; k++){
        for (int i = 1; i < jump[k-1].size(); i++){
            int p1 = jump[k-1][i] + 1;
            if (p1 >= jump[k-1].size()) break;
            jump[k].push_back(jump[k-1][p1]);
        }
    }
    // for (int i = 0; i < lg; i++){
    //     cout << i << ": ";
    //     for (int j: jump[i]) {
    //         cout << j << " ";
    //     }
    //     cout << "\n";
    // }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int rs = 0;
        for (int i = lg - 1; i >= 0; i--){
            while (jump[i].size() > l && jump[i][l] <= r) {
                // cerr << i << " " << l << "\n";
                rs+=(1 << i);
                l = jump[i][l] + 1;
            }
        }
        cout << rs << "\n";
    };
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 1; i < jump[k-1].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
sumzero.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if (p1 >= jump[k-1].size()) break;
      |                 ~~~^~~~~~~~~~~~~~~~~~~
sumzero.cpp:49:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |             while (jump[i].size() > l && jump[i][l] <= r) {
      |                    ~~~~~~~~~~~~~~~^~~

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