# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
112656771 |
Practice:
Loke_0 |
1333C
- 21
|
C++17 (GCC 9-64)
|
Time limit exceeded on test 88
|
1500 ms
|
10108 KB
|
2021-04-11 16:21:44 |
2021-04-11 16:21:44 |
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
string alpha_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alpha_lower = "abcdefghijklmnopqrstuvwxyz";
double eps = 1e-12;
#define mod 1000000007
#define inf 1e18
#define pb push_back
#define endl "\n"
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define ps(x, y) fixed<<setprecision(y)<<x
#define print(anything) for(auto i: anything)cout<<i<<" ";
#define debug(x) cerr<<#x<<" : "<<x<<" "<<endl;
template <class Tm1, class Tm2>
void print_map(map<Tm1, Tm2> m){
for(auto it = m.begin(); it != m.end(); it++){
cout << (*it).first << " : " << (*it).second << endl;
}
}
/*
$$ Understand Question in "ABSTRACT" way
$$ Check the CONSTRAINTS
$$ Check For any CORNER TEST CASES
$$ Design Algorithm
*/
void solve(){
ll n, ans = 0;
cin >> n;
v64 v(n);
unordered_map<ll, ll> sums;
for (ll i = 0; i < n; i++)
{
cin >> v[i];
if(v[i]) ans++;
}
ll pref = 0, start = 0, end = 0;
for (ll i = 0; i < n && end < n && start <= end; i += 1)
{
if(!v[i]){
start = i+1;
end = i+1;
continue;
}
pref += v[i];
if(sums[pref] > start || !pref){
if(!pref) start++, pref = v[i];
else start = sums[pref]+1;
}
ans += max(0LL, end-start);
end++;
sums[pref] = i+1;
}
cout << ans << endl;
}
int main()
{
fast_cin();
solve();
return 0;
}
Click to see test details