Submission #1136241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136241		hypersphere	Sum Zero (RMI20_sumzero)	C++20	61 / 100	243 ms	23892 KiB

sumzero

// This is your sign to stop stalking
// Save at User name to source repo

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <string>
#include <stack>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stdio.h>
#include <cstdlib>

#pragma region Helpers
#define printArr(a) for(int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << "\n";
#define printArrWithComma(a) for(int i = 0; i < a.size(); i++) cout << a[i] << ", "; cout << "\n";
#define printArrIgnore0(a) for(int i = 1; i < a.size(); i++) cout << a[i] << " "; cout << "\n";
#define checkpoint(n) cout << "Checkpoint " << n << "\n";


using namespace std;

long long binpow(long long base, long long power, long long mod) {
    if (base == 0) return 0;
    if (base == 1) return 1;
    if (power == 0) return 1;
    long long multiplier = (power % 2 == 0 ? 1 : base);
    return (binpow((base * base) % mod, power / 2, mod) * multiplier) % mod;
}
const long long mod = 1000000007;
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
long long factorial(long long n) {
    long long ans = 1;
    for (long long i = 1; i <= n; i++) ans *= i;
    return ans;
}
const long long INF = 1000000000000000;
#pragma endregion

struct Query {
    int l, r, idx;
    Query() : l(0), r(0), idx(0) {

    }
    Query(int l, int r, int idx) : l(l), r(r), idx(idx) {

    }
};

int lg;
void Run() {
    int n;
    cin >> n;
    lg = ceil(log2(n));
    vector<int> arr(n + 1, -1);
    long long pref = 0;
    vector<vector<int>> up(1, vector<int>(n + 1, -1));
    map<long long, int> mp;
    mp[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        pref += arr[i];
        up[0][i] = up[0][i - 1];
        if (mp.count(pref)) {
            up[0][i] = max(up[0][i - 1], mp[pref]);
        }
        mp[pref] = i;
    }
    int q;
    cin >> q;
    vector<Query> queries(q);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }
    for (int i = lg - 1; i >= 0; i--)
    {
        for (int j = n; j >= 1; j--) arr[j] = up[0][j];
        //for (int j = 1; j <= n; j++) cout << arr[j] << " ";
        //cout << "\nCP1\n";
        for (int j = 1; j <= i; j++)
        {
            for (int k = n; k >= 1; k--) if(arr[k] != -1) arr[k] = arr[arr[k]];
        }
        //for (int j = 1; j <= n; j++) cout << arr[j] << " ";
        //cout << "\nCP2\n";
        for (int j = 0; j < q; j++) if (arr[queries[j].r] >= queries[j].l - 1) queries[j].r = arr[queries[j].r], ans[j] += (1 << i);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tests = 1;
    //cin >> tests;
    auto start = clock();
    while (tests--) Run();
    auto end = clock();
    cerr << "Time: " << end - start << " (ms)\n";
}

/* 
5 3
1 5 4
2 3 5
1 2 4
*/
// Code by an idiot

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