제출 #1010360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010360		HUECTRUM	Sum Zero (RMI20_sumzero)	C++14	61 / 100	1020 ms	59868 KiB

sumzero

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_set>
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bitset>
#include <sstream>
#include <ext/rope>
#include <ctime>
#include <random>
#include <cstdlib>
#include <complex>
#include <iomanip>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

/* clang-format off */

/* TYPES  */
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pair<int, int>>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vpll vector<pair<long long, long long>>
#define vvpll vector<vector<pair<long long, long long>>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define mii map<int, int>
#define si set<int>
#define sc set<char>



/* FUNCTIONS */
#define feach(el, v) for(auto &el: v)
#define rep(i, n) for(int i=0;i<n;i++)
#define reprv(i, n) for(int i=n-1;i>=0;i--)
#define reps(i, s, e) for(int i=s;i<e;i++)
#define reprve(i, e, s) for(int i=e;i>=s;i--)
#define repe(x, y) for (auto &x: y)
#define repe2(x, a, y) for (auto &[x,a]: y)

typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oSet;

//////////////////////////////////////////////////////



const int LOG = 19;

int main() {
    int n; cin >> n;
    ll x, pref = 0;

    vll prefSums(n);

    map<ll, vi> prefIdxs;
    rep(i, n) cin >> x, pref += x, prefSums[i] = pref, prefIdxs[pref].push_back(i);

    vvi binLift(LOG, vi(n + 2));

    binLift[0][0] = prefIdxs.count(0) ? prefIdxs[0][0] + 1 : n + 1;
    reps(i, 1, n) {
        ll curPref = prefSums[i - 1];
        auto t = lower_bound(prefIdxs[curPref].begin(), prefIdxs[curPref].end(), i);
        binLift[0][i] = (t == prefIdxs[curPref].end()) ? n + 1 : *t + 1;
    }
    reprv(i, n - 1) binLift[0][i] = min(binLift[0][i], binLift[0][i + 1]);
    binLift[0][n] = binLift[0][n + 1] = n + 1;
    reps(lg, 1, LOG) rep(i, n + 2) {
        binLift[lg][i] = binLift[lg - 1][binLift[lg - 1][i]];
    }

    int q, l, r; cin >> q;
    rep(i, q) {
        cin >> l >> r; --l, --r;
        int ans = 0;
        reprv(lg, LOG) if (binLift[lg][l] <= r + 1) l = binLift[lg][l], ans += (1 << lg);
        cout << ans << endl;
    }
}

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