Submission #942700

#	Time	Username	Problem	Language	Result	Execution time	Memory
942700		vjudge1	Sum Zero (RMI20_sumzero)	C++17	100 / 100	462 ms	8276 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
const int BSIZE = 73;

vector<int> p0, p1, p2;

void input(){
    int n; cin >> n;

    vector<pair<long long, int>> pf(n+1);
    for (int i=1; i<=n; i++){
        int v; cin >> v;
        pf[i] = {pf[i-1].first + v, i};
    }
    sort(pf.begin(), pf.end());

    p0.assign(n+1, INT_MIN);
    for (int lptr=0, rptr=0; lptr<pf.size(); lptr=rptr)
        for (rptr++; rptr < pf.size() && pf[lptr].first == pf[rptr].first; rptr++)
            p0[pf[rptr].second] = pf[rptr-1].second;
    
    for (int i=1; i<p0.size(); i++)
        p0[i] = max(p0[i], p0[i-1]);
}

void build(const vector<int> &ps, vector<int> &pl){
    pl.assign(ps.size(), INT_MIN);
    for (int i=0; i<pl.size(); i++){
        pl[i] = i;
        for (int j=0; j<BSIZE && pl[i] != INT_MIN; j++)
            pl[i] = ps[pl[i]];
    }
}

int jmp(const vector<int> &p, int l, int &r){
    int v = 0;
    for (; p[r] + 1 >= l; r = p[r])
        v++;
    return v;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    input();
    build(p0, p1);
    build(p1, p2);

    int q; cin >> q;
    while (q--){
        int l, r; cin >> l >> r;
        int v = 0;
        v += jmp(p2, l, r) * BSIZE * BSIZE;
        v += jmp(p1, l, r) * BSIZE;
        v += jmp(p0, l, r);
        cout << v << "\n";
    }
}

Compilation message (stderr)

sumzero.cpp: In function 'void input()':
sumzero.cpp:18:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int lptr=0, rptr=0; lptr<pf.size(); lptr=rptr)
      |                              ~~~~^~~~~~~~~~
sumzero.cpp:19:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (rptr++; rptr < pf.size() && pf[lptr].first == pf[rptr].first; rptr++)
      |                      ~~~~~^~~~~~~~~~~
sumzero.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=1; i<p0.size(); i++)
      |                   ~^~~~~~~~~~
sumzero.cpp: In function 'void build(const std::vector<int>&, std::vector<int>&)':
sumzero.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=0; i<pl.size(); i++){
      |                   ~^~~~~~~~~~

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