제출 #1095499

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

sumzero

#include <iostream>
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pbds tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>aaaaaaa
#define fr first
#define sc second
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define lll long long int
#define ld long double
#define p(x,y) cout<<fixed<<setprecision(y)<<x<<"\n";
#define PI 3.1415926535897
#define mem(dp) memset(dp, -1, sizeof dp)
#define ones(x) __builtin_popcountll(x)
#define acc(a, n) accumulate(a, a + n,0ll);
#define ac(a, n) accumulate(a.begin(), a.begin() + n, 0ll)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(X) ((ll)(X).size())
#define lcm(a, b) (a / __gcd(a,b) * b)
#define pll pair<ll, ll>
#define pi pair<int, int>
#define pb push_back
#define in insert
#define vll vector<ll>
#define vi vector<int>
#define al(it) it.fr << " " << it.sc << "\n"
#define _cout(v)  for(auto f : v ) cout << f << " " ;
#define _cin(v)   for(auto &it : v)cin >> it ;
#define Tmax(type)   std::numeric_limits<type>::max()
#define Tmin(type)   std::numeric_limits<type>::min()
#define debug(x) cout<<" [ " << #x << " is: " << x << " ] "<<endl
#define mod (ll)1000000007
//#define mod (ll)998244353
#define POW2(x) (1 << x)
#define N 200001
#define d(a) a - 'a'
using namespace std;
const int L = 20;
int main()
{
    Fast;
    int n;
    cin >> n;

    vector<int>a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(i)
            a[i] += a[i - 1];
    }

    int dp[n + 1][L];

    mem(dp);
    unordered_map<ll, int>seen;
    int last = -1;
    for(int i = n - 1; i >= 0; i--)
    {
        seen[a[i]] = i;
        if(i)
        {
            if(seen.count(a[i - 1]))
            {
                dp[i][0] = seen[a[i - 1]] + 1;
                if(~last)
                    dp[i][0] = min(dp[i][0], last);
                last = dp[i][0];
            }
            else
            {
                dp[i][0] = last;
            }

        }
        else
        {
            if(seen.count(0))
            {
                dp[i][0] = seen[0] + 1;
                if(~last)
                    dp[i][0] = min(dp[i][0], last);
                last = dp[i][0];
            }
            else
            {
                dp[i][0] = last;
            }
        }
    }

    for(int i = 1; i < L; i++)
    {
        for(int j = 0; j < n; j++)
        {

            if(dp[j][i - 1] != -1)
            {
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
            }
        }
    }

    int q;
    cin >> q;
   int cur = 0, ans = 0;int l, r;
    while(q--)
    {

        cin >> l >> r;

        l--, r--;
        cur = l, ans = 0;
        for(int i = L - 1; i >= 0; i--)
        {
            if((~dp[cur][i]) and dp[cur][i] - 1 <= r)
            {
                cur = dp[cur][i];
                ans += (1 << i);
            }
        }
        cout << ans << "\n";

    }
}

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