https://codeforces.com/contest/1333/problem/C
<문제설명>
-1e9~1e9값을 갖는 최대 1e5의 원소 n개의 배열이 주어진다.
배열의 subarray 중 그 subarray의 subarray의 원소합이 0이 아니면 good subarray라고 한다.
주어진 배열의 good subarray 개수를 구하라
<풀이>
[a1, a2, a3, a4]가 good subarray라면 [a1,a2,a3]도 good subarray이다. 하지만 [a3,a4]가 good subarray일수도 있고 아닐수도 있다.
ps[1] = ps[4]인 경우 a[2]~a[4]는 bad subarray이다.
문제의 성질을 잘 생각해보면 투포인터로 풀 수 있다.
<코드>
ll n, a[MAX], ps[MAX];
int main() {
FAST; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ps[i] = ps[i - 1] + a[i];
}
set<ll> s;
ll lo = 0, hi=0, ans=0;
s.insert(0);
while (lo < n) {
while (hi < n && !s.count(ps[hi + 1])) {
hi++;
s.insert(ps[hi]);
}
ans += hi - lo;
s.erase(ps[lo]);
++lo;
}
cout << ans << '\n';
}
'알고리즘 > 코드포스' 카테고리의 다른 글
2019-2020 ICPC, Asia Jakarta Regional - H. Twin Buildings(수학, 기하) (0) | 2020.04.20 |
---|---|
cf #621 div1&2 D - Cow and Fields (그리디, 정렬, 그래프) (0) | 2020.04.17 |
cf #538 div2 C - Trailing Loves (소인수분해, 수학) (0) | 2020.04.02 |
cf #630 div2 E - Height all the same (수학, 집합) (0) | 2020.04.01 |
cf 551 div2 D - Serval and Rooted Tree (tree, dp, 발상) (0) | 2020.03.25 |