Submission #1243131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243131		asdfghqwert	Sum Zero (RMI20_sumzero)	C++20	0 / 100	7 ms	832 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(){
    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];
        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;
                mp.erase(arr[j]);
            }
            lst = k + 2;
            mp[val] = k + 1;
        }mp[arr[i]] = i;
        val = arr[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];
            //cout << j << ' ' << (1 << i) << ' ' << dp[j][i] << '\n';
        }
    }
    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: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39