Submission #1242000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242000		hynmj	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	1856 KiB

sumzero

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
template <typename T> using v = vector<T>;
const int INF = 1e18, MOD = 1e9+7, N = 2e5+7;
vi primes;
int seen[N+1];
int st[N][32];
void findPrimes()
{
    for (int i=2;i*i<=N ;i++)
    {
        if (seen[i])continue;
        primes.append(i);
        for (int j=i*2;j<=N;j+=i)
        {
            seen[j]=1;
        }
    }
}
void solve()
{
    int q,n, k, e, m, ans = 0;
    cin >> n ;
    vi a(n);
    rep(n)
    {
    	cin >> e;a[i]=e;
    }
    map<int,vi> graph;
    vi pref(n+1,0);
    for (int i=1;i<=n;i++)
    {
        pref[i]+=pref[i-1] + a[i-1];
    }
    rep(n+2)st[i][0]=n+1;
    map<int,int> last;
    last[0] = n;
    for (int i=n;i>=0;i--)
    {
        if (last[pref[i]]!=0)
            st[i][0] = last[pref[i]];
        last[pref[i]]= i; 
    }

    // vi next(n+1,n+1);
    for (auto i: graph)
    {
        vi &b = i.ss;
        int n=b.size();
        rep(n-1)
        {
            st[b[i]][0]=min(st[b[i]][0],b[i+1]);
        } 
    }
    
    per(n+1)
        st[i][0]=min(st[i][0],st[i+1][0]);
    
    for (int p=1;p<22;p++)
    {
        for (int i=0;i<=n+1;i++)
        {
            st[i][p]=st[st[i][p-1]][p-1];

        }
    }
    
    int l,r;
    cin >>q;
    rep(q)
    {
        cin >> l >> r;
        ans=0;
        l--;
        // cout << l <<" ";
        // cout << endl;
        for (int i=20;i>=0;i--)
        {
            
            if (st[l][i]<=r)
            {
                // cout << "jumped "<<(1ll<<i)<< " steps ahead"<< endl;
                // cout << l <<" ";
                l = st[l][i];
                // cout << l <<" ";
                l++;
                ans+=(1ll<<i);
                // cout<< " ans  = "<< ans << endl; 
                // cout << endl;
            }
        }
        cout <<ans << " ";
    }


    // rep(n+1)cout << st[i][0]<< " ";
    // ln;
    // rep(n+1)cout << st[i][1]<< " ";

     // cout << ans;
    // cout << a.size();
    // for (auto i: next){cout << i << " ";}
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    rep(ans){
        // cout << "Case #" << i+1 << ": ";
        solve();ln;}}

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