제출 #398523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398523		model_code	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1089 ms	14200 KiB

sumzero

/**
* user:  test
* fname: Test
* lname: Testulescu
* task:  SumZero
* score: 61.0
* date:  2020-11-29 14:58:36.504236
*/
#include <bits/stdc++.h>
#define inf 1000000000
using namespace std;

vector <int> compute_lift(int n)
{
    vector <pair <long long, int>> mp(n + 1);
    mp[0] = { 0, 0 };

    long long sp = 0;
    vector <int> ans(n + 1, inf);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sp += x;
        mp[i] = { sp, i };
    }

    sort(mp.begin(), mp.end());
    for (int i = 1; i < (int)mp.size(); i++)
        if (mp[i].first == mp[i - 1].first)
            ans[mp[i - 1].second] = mp[i].second;

    for (int i = n - 1; i >= 0; i--)
        ans[i] = min(ans[i], ans[i + 1]);
    return ans;
}

int main()
{
    int n;
    cin >> n;

    vector <vector <int>> lift;
    lift.emplace_back(compute_lift(n));

    for (int i = 1; i < 8; i++) {
        lift.emplace_back(n + 1, inf);
        for (int j = 0; j < n; j++) {
            int act = j;
            for (int k = 0; k < 4; k++)
                if (act != inf)
                    act = lift[i - 1][act];
            lift[i][j] = act;
        }
    }

    int q;
    cin >> q;

    for (int test = 0; test < q; test++) {
        int L, R;
        cin >> L >> R;

        L--;
        int rez = 0;

        for (int i = (int)lift.size() - 1; i >= 0; i--)
            while (lift[i][L] <= R)
                rez += (1 << (2 * i)), L = lift[i][L];

        cout << rez << '\n';
    }

    return 0;
}

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