Submission #646680

#	Time	Username	Problem	Language	Result	Execution time	Memory
646680		Vanilla	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1099 ms	22440 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 4e5 + 5;
const int lg = 7;
vector <int> jump [lg];
int ps [maxn];
int64 pref [maxn];
 
int main() {
    ios::sync_with_stdio(0);cin.tie(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 = 0; i < maxn; i++) ps[i] = -1;
    vector <int64> norm = {0};
    for (int i = 1; i <= n; i++){
        cin >> a;
        pref[i] = pref[i-1] + a;
        norm.push_back(pref[i]);
    }
    sort(norm.begin(), norm.end());
    ps[lower_bound(norm.begin(), norm.end(), 0) - norm.begin()] = 0;
    for (int i = 1; i <= n; i++){
        int k = lower_bound(norm.begin(), norm.end(), pref[i]) - norm.begin();
        if (ps[k] != -1) {
            jump[0][ps[k] + 1] = i;
        }
        ps[k] = 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]);
        }
    }
    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) {
                rs+=(1 << i);
                l = jump[i][l] + 1;
            }
        }
        cout << rs << "\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:50:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |             while (jump[i].size() > l && jump[i][l] <= r) {
      |                    ~~~~~~~~~~~~~~~^~~
sumzero.cpp:14:11: warning: unused variable 's' [-Wunused-variable]
   14 |     int64 s = 0, a = 0;
      |           ^

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