Submission #753342

#	Time	Username	Problem	Language	Result	Execution time	Memory
753342		lukameladze	Sum Zero (RMI20_sumzero)	C++14	22 / 100	134 ms	33780 KiB

sumzero

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, inf = 1e9;
int t, n, a[N],par[N][21],pr[N],nxt[N];
map <int, int> mp;
int tree[N];
vector <int> vec[N];
void upd(int idx, int val) {
    for (int i = idx; i > 0; i -= i&(-i)) tree[i] = min(tree[i], val);
}
int getmn(int idx) { // suffix query
    int pas = n + 1;
    for (int i = idx; i < N; i += i&(-i)) pas = min(pas, tree[i]);
    return pas;
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        pr[i] = pr[i - 1] + a[i];
        nxt[i] = -1;
    }
    mp[pr[0]] = 0;
    for (int i = 1; i <= n; i++) {
        if (mp[pr[i]] != 0 || pr[i] == 0) {
            vec[mp[pr[i]] + 1].pb(i);
            nxt[mp[pr[i]] + 1] = i;
        }
        mp[pr[i]] = i;
    }
    int mn = inf;
    vector <pii> v;
    for (int i = n; i >= 1; i--) {
        if (nxt[i] == -1) continue;
        if (mn <= nxt[i]) continue;
        v.pb({i, nxt[i]});
        mn = min(mn, nxt[i]);
    }
    sort(v.begin(), v.end()); // if (l[i] > l[j]) ---> r[i] > r[j]
    int m = v.size();
    for (int i = 1; i < N; i++) tree[i] = n + 1;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        par[i + 1][0] = getmn(v[i].s + 1);
        upd(v[i].f, i + 1);
    }
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            if (par[i][j - 1] == n + 1) par[i][j] = n + 1;
            else par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
    for (int i = 0; i < v.size(); i++) {
        //cout<<v[i].f<<" --> "<<v[i].s<<"\n";
    }
    int q; cin>>q;
    while (q--) {
        int le, ri;
        cin>>le>>ri;
        int st_idx = getmn(le);
        if (st_idx == n + 1 || v[st_idx - 1].f > ri) {
            cout<<0<<"\n"; continue;
        }
        int cur = st_idx;
        int ans = 0;
        for (int i = 20; i >= 0; i--) {
            if (par[cur][i] != n + 1 && v[par[cur][i] - 1].f <= ri) cur = par[cur][i], ans += (1<<i);
        }
        if (v[cur - 1].s <= ri) ans++;
        cout<<ans<<"\n";
    }
}

Compilation message (stderr)

sumzero.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~
sumzero.cpp: In function 'int main()':
sumzero.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
sumzero.cpp:46:9: warning: unused variable 'm' [-Wunused-variable]
   46 |     int m = v.size();
      |         ^

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