Submission #646654

#	Time	Username	Problem	Language	Result	Execution time	Memory
646654		Vanilla	Sum Zero (RMI20_sumzero)	C++17	61 / 100	539 ms	41876 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 4e5 + 5;
const int lg = 19;
int64 a [maxn];
map <int64, int> ps;
int l [maxn];
vector <int> jump [lg];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i <= n + 1; i++){
        l[i] = n + 1;
    }
    ps[0] = 0;
    int64 s = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        s+=a[i];
        if (ps.count(s)) {
            l[ps[s] + 1] = i;
        }
        ps[s] = i;
    }
    for (int i = n; i >= 1; i--){
        l[i] = min(l[i], l[i + 1]);
    }
    for (int i = 0; i < lg; i++) jump[i].push_back(0);
    for (int i = 1; i <= n; i++){
        jump[0].push_back(l[i]);
    }
    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";
    };
    
    
    // for (auto i: sv){
    //     cout << i.first << " " << i.second << "\n";
    // }
}

Compilation message (stderr)

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

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