Submission #846889

#	Time	Username	Problem	Language	Result	Execution time	Memory
846889		TahirAliyev	Sum Zero (RMI20_sumzero)	C++17	22 / 100	1029 ms	8916 KiB

sumzero

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<int, int>

const int MAX = 4e5 + 5;

int n, q;
int arr[MAX];
int presum[MAX];
int R[MAX];
int dp[MAX];

int main(){
    cin >> n;
    set<pii> s;
    s.insert({0, 0});
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        presum[i] = presum[i - 1] + arr[i];
        s.insert({presum[i], i});
    }
    for(int l = 0; l < n; l++){
        s.erase(s.find({presum[l], l}));
        auto itr = s.lower_bound({presum[l], 0});
        if(itr == s.end() || (*itr).first != presum[l]) continue;
        R[l + 1] = (*itr).second;
    }
    cin >> q;
    while(q--){
        memset(dp, 0, sizeof(dp));
        int l, r; cin >> l >> r;
        for(int i = r; i >= l; i--){
            if(R[i] > r || R[i] == 0){
                dp[i] = dp[i + 1];
                continue;
            }
            dp[i] = max(dp[i + 1], dp[R[i] + 1] + 1);
        }
        cout << dp[l] << '\n';
    }
}

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