Submission #1272528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272528		algoproclub	Sum Zero (RMI20_sumzero)	C++20	100 / 100	256 ms	19464 KiB

sumzero

// UUID: 91922bf0-284a-4982-a10e-abd41fe6d49d

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG
namespace debug {
int dbg_rec = 0;
 
template <typename T, typename... U>
concept IsAnyOf = (std::same_as<T, U> || ...);
 
template<typename T>
concept IsCont = IsAnyOf<T, std::vector<typename T::value_type>, 
std::set<typename T::value_type>,
std::multiset<typename T::value_type>>;
 
template<typename Ostream, IsCont Cont> 
Ostream& operator<<(Ostream& os,  const Cont v){ os<<"["; for(auto& x : v){os<<x<<", ";} os<<"]"; return os; }
 
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
    os<<"{"<<p.first<<", "<<p.second<<"}"; return os;
}
 
template<typename T>
void print_dbg(stringstream& ss, T x) { ss << x; }
template<typename T, typename... Args>
void print_dbg(stringstream& ss, T x, Args... args) { ss << x << ", "; print_dbg(ss, args...); }
}
#define dbg(...) {stringstream ss; ++debug::dbg_rec; debug::print_dbg(ss, __VA_ARGS__); --debug::dbg_rec; cerr << string(debug::dbg_rec, '\t') << "\e[91m" << __func__ << ":" << __LINE__ << '\t' << #__VA_ARGS__ << " = " << ss.str() << "\e[39m" << endl; }
#define ASSERT(x) assert((x))
#else
#define dbg(...)
#define ASSERT(x)
#endif
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    vector<long long> v(n);
    for(auto &x : v) cin>>x;

    for(int i = 1; i < n; i++) v[i] += v[i-1];

    vector<int> to(n, -1);
    { // to delete map from memory
        map<long long, int> mp;
        mp[0] = -1;
        int last = -1;
        for(int i = 0; i < n; i++) {
            if(mp.count(v[i])) last = max(mp[v[i]] + 1, last);
            mp[v[i]] = i;
            to[i] = last;
        }
    }
    vector<int> to2(n, -1), len(n, 1);
    for(int i = 0; i < n; i++) {
        int j = to[i];
        if(j > 0 && to2[j-1] > 0 && to2[to2[j-1]-1] > -1 && len[j-1] == len[to2[j-1]-1]) {
            to2[i] = to2[to2[j-1]-1];
            len[i] = 1 + len[j-1] * 2;
        } else {
            to2[i] = to[i];
            len[i] = to[i] >= 0 ? 1 : 0; 
        }
    }

    int q;
    cin>>q;
    while(q--) {
        int l, r;
        cin>>l>>r;
        --l, --r;

        int ans = 0, x = r;
        while(x >= l) {
            if(to2[x] >= l) {
                ans += len[x];
                x = to2[x] - 1;
            } else {
                if(to[x] >= l) ans++; 
                x = to[x] - 1;
            }   
        }
        cout << ans << '\n';
    }

    return 0;
}

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