Submission #1243202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243202		asdfghqwert	Sum Zero (RMI20_sumzero)	C++20	61 / 100	321 ms	47480 KiB

sumzero

//#pragma GCC optimize("O3,unroll-loops,fast-math")
//#pragma GCC optimize("O3,Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n ;cin >> n;
    const int lg = 23;
    const int N = n + 10;
    int dp[N][lg] , arr[N] , lst = 1 , val = 0;
    memset(dp , 0 , sizeof(dp));
    map<int , int> mp;mp[0] = 0;
    for(int i = 1 ; i <= n ; i++){
        cin >> arr[i];
        val += arr[i];
        arr[i] = val;
        if(mp.count(arr[i])){
            int k = mp[arr[i]];
            for(int j = lst ; j <= k + 1; j++){
                dp[j][0] = i;
            }
            lst = max(k + 2 , lst);
        }
        mp[arr[i]] = i;
    }
   // for(int i = 1 ; i <= n ; i++)cout << dp[i][0] << ' ';
    for(int i = 1 ; i < lg ; i++){
        for(int j = 1 ; j <= n ; j++){
            if(dp[j][i - 1] == 0)break;
            dp[j][i] = dp[dp[j][i - 1] + 1][i - 1];
        }
    }
    int q; cin >> q;
    while(q--){
        int cur ,r , ans = 0;
        cin >> cur >> r;
        for(int j = lg - 1 ; j >= 0 ; j--){
            if(cur > r)break;
            if(dp[cur][j] <= r && dp[cur][j] > 0){
                ans += (1 << j);
                cur = dp[cur][j] + 1;
            }
        }
        cout << ans << '\n';
    }
}

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