Submission #517113

#	Time	Username	Problem	Language	Result	Execution time	Memory
517113		Stickfish	Sum Zero (RMI20_sumzero)	C++17	22 / 100	1075 ms	6832 KiB

sumzero

#include <iostream>
#include <cassert>
#include <map>
#include <vector>
#include <bitset>
using namespace std;
using ll = long long;
#define endl '\n'

const int MAXN = 400000;
int a[MAXN];

struct stree {
    void assign(int n) {
        sz = n;
        t.resize(sz * 2 - 1);
        assign(0, 0, sz);
    }

    int get(int l, int r) {
        pair<int, int> ans = get(0, 0, sz, l, r);
        if (ans.first + 1 < l)
            return ans.second - 1;
        return ans.second;
    }
 private:
     int sz;
     vector<pair<int, int>> t;

     vector<pair<int, int>> assign(int ind, int lnd, int rnd) {
         if (rnd - lnd == 1) {
             t[ind] = {a[lnd], 1};
             //cout << lnd << ' ' << rnd << ": " << t[ind].first << ' ' << t[ind].second;
             return {t[ind]};
         }
         int mnd = (lnd + rnd) / 2;
         int chd = ind + (mnd - lnd) * 2;
         vector<pair<int, int>> vl = assign(ind + 1, lnd, mnd);
         vector<pair<int, int>> vr = assign(chd, mnd, rnd);
         for (auto [j, cnt] : vr) {
             if (j < lnd)
                 vl.push_back({j, cnt});
             else
                 vl.push_back({vl[j - lnd].first, cnt + vl[j - lnd].second});
         }
         t[ind] = vl.back();
         vr.clear();
         return vl;
     }

     pair<int, int> get(int ind, int lnd, int rnd, int l, int r) {
         if (l <= lnd && rnd <= r) {
             return t[ind];
         }
         int mnd = (lnd + rnd) / 2;
         if (mnd >= r) {
             return get(ind + 1, lnd, mnd, l, r);
         }
         int chd = ind + (mnd - lnd) * 2;
         pair<int, int> p = get(chd, mnd, rnd, l, r);
         if (p.first >= lnd && p.first >= l) {
             pair<int, int> q = get(ind + 1, lnd, mnd, l, p.first + 1);
             return {q.first, q.second + p.second};
         } else {
             return p;
         }
     }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    map<ll, int> mp;
    mp[0] = -1;
    ll psm = 0;
    for (int i = 0; i < n; ++i) {
        psm += a[i];
        if (mp.find(psm) == mp.end()) {
            a[i] = -2;
        } else {
            a[i] = mp[psm];
        }
        if (i && a[i - 1] > a[i]) {
            a[i] = a[i - 1];
        }
        mp[psm] = i;
    }
    stree tr;
    tr.assign(n);
    mp.clear();
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        cout << tr.get(l, r) << endl;
    }
}

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