oj.uz

Submission #926732

# Submission time Handle Problem Language Result Execution time Memory
926732 2024-02-13T14:52:35 Z TimDee Sum Zero (RMI20_sumzero) C++17
100 / 100
 944 ms 16032 KB 
//  Esti <3

//\
     šťastia pre nás :)
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const ll inf = 1e18;
//const ll mod = 998244353;

// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts:  :smiling_face_with_3_hearts:  
 
//vidime sa veľmi skoro, moje slnko

//[] {}

//кто андрей столетний - того на вилы

const int N=4e5+5;
const int K=600;
int par[N];
int go[N];
int n,q;
int u,i,j;
int l,r;
int ans;
int s=0;
unordered_map<int,int> m;
int a[N];
//i'm not retarded, it's ml retarded

void solve() {

    cin>>n;
    for(i=0; i<n; ++i) cin>>a[i];
    
    m[0]=n;

    for(i=0; i<n+1; ++i) par[i]=n+1;
    for(i=n-1; i>=0; --i) {
        s+=a[i];
        if (m.count(s)) par[i]=m[s];
        m[s]=i;
    }
    m.clear();

    u=n+1;
    for(i=n-1; i>=0; --i) {
        if (par[i]>-1) u=min(u,par[i]);
        par[i]=u;
    }

    for(i=0; i<n; ++i) {
        u=i;
        for(j=0; j<K && u<=n; ++j) {
            u=par[u];
        }
        go[i]=u;
    }

    cin>>q;
    for(i=0;i<q;++i) {
        cin>>l>>r;
        u=l-1;
        ans=0;
        while (go[u] <= r) {
            ans+=K;
            u=go[u];
        }
        while (par[u] <= r) {
            ++ans;
            u = par[u];
        }
        cout<<ans<<'\n';
    }

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1; 
    //cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message

sumzero.cpp:3:1: warning: multi-line comment [-Wcomment]
    3 | //\
      | ^
sumzero.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //   \ __ __  \
      | ^
sumzero.cpp:36:1: warning: multi-line comment [-Wcomment]
   36 | // \
      | ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4444 KB Output is correct
2 Correct 3 ms 4532 KB Output is correct
3 Correct 7 ms 4700 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 7 ms 4732 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4444 KB Output is correct
2 Correct 3 ms 4532 KB Output is correct
3 Correct 7 ms 4700 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 7 ms 4732 KB Output is correct
7 Correct 190 ms 6576 KB Output is correct
8 Correct 143 ms 7260 KB Output is correct
9 Correct 201 ms 5556 KB Output is correct
10 Correct 189 ms 6552 KB Output is correct
11 Correct 171 ms 6572 KB Output is correct
12 Correct 199 ms 5716 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4444 KB Output is correct
2 Correct 3 ms 4532 KB Output is correct
3 Correct 7 ms 4700 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 7 ms 4732 KB Output is correct
7 Correct 190 ms 6576 KB Output is correct
8 Correct 143 ms 7260 KB Output is correct
9 Correct 201 ms 5556 KB Output is correct
10 Correct 189 ms 6552 KB Output is correct
11 Correct 171 ms 6572 KB Output is correct
12 Correct 199 ms 5716 KB Output is correct
13 Correct 893 ms 13592 KB Output is correct
14 Correct 795 ms 15740 KB Output is correct
15 Correct 944 ms 7952 KB Output is correct
16 Correct 878 ms 16032 KB Output is correct
17 Correct 829 ms 12752 KB Output is correct
18 Correct 937 ms 8052 KB Output is correct