Submission #1140672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140672		azaylibelz	Sum Zero (RMI20_sumzero)	C++17	0 / 100	64 ms	76608 KiB

sumzero

#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iterator>
#include <stack>
#include <queue>
#include <set>

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7;
const ll lg = 4, maxn = 4e5 + 1, base = 32;
vector<vector<ll>> sparseTable(maxn, vector<ll>(lg));
vector<ll> power(lg);

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("D:/C++ Project/test/seg-tre-e/LCA+BL/input.txt", "r", stdin);
    #endif // !ONLINE_JUDGE
    power[0] = 1;
    for (int i = 1; i < lg; i++) power[i] = base * power[i - 1];
    ll n; cin >> n;
    vector<ll> arr(n);
    for(ll i = 0; i < n; i++) cin >> arr[i];
    for(ll i = 0; i <= n + 1; i++) {
        for(ll j = 0; j < lg; j++) {
            sparseTable[i][j] = n + 1;
        }
    }
    ll sm = 0;
    vector<ll> pSum;
    pSum.push_back(0);
    for(ll i = n - 1; i >= 0; i--) {
        sm += arr[i];
        pSum.push_back(sm);
    }
    sort(pSum.begin(), pSum.end());
    pSum.resize(unique(pSum.begin(), pSum.end()) - pSum.begin());
    sm = 0;
    vector<ll> go(pSum.size(), n + 1);
    go[lower_bound(pSum.begin(), pSum.end(), sm) - pSum.begin()] = n;
    for(ll i = n - 1; i >= 0; i--) {
        sm += arr[i];
        sparseTable[i][0] = go[lower_bound(pSum.begin(), pSum.end(), sm) - pSum.begin()];
        go[lower_bound(pSum.begin(), pSum.end(), sm) - pSum.begin()] = i;
    }
    for(ll i = n - 2; i >= 0; i--) {
        sparseTable[i][0] = min(sparseTable[i][0], sparseTable[i + 1][0]);
    }
    for (ll j = 1; j < lg; j++) {
        for (ll i = 0; i < n; i++) {
            ll x = i;
            for(ll k = 0; k < base; k++) 
                x = sparseTable[x][j - 1];
            sparseTable[i][j] = x;
        }
    }
    ll q; cin >> q;
    for(ll i = 0; i < q; i++) {
        ll l, r, res = 0; cin >> l >> r; l--;
        ll x = lg - 1;
        while(x >= 0) {
            if(sparseTable[l][x] > r) x--;
            else {
                res += power[x];
                l = sparseTable[l][x];
            }
        }
        cout << res << "\n";
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("D:/C++ Project/test/seg-tre-e/LCA+BL/input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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