| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 942912 | vjudge1 | Nicelines (RMI20_nicelines) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define nl '\n'
#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int64_t> p(n + 1);
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
p[i + 1] = p[i] + x;
}
std::vector<int> R(n + 1);
std::vector<int> jump(n + 2), depth(n + 2), parent(n + 2);
jump[n + 1] = n + 1;
std::map<int64_t, int> mp;
for (int i = n, to = n + 1; i >= 0; i--) {
auto it = mp.find(p[i]);
if (it == mp.end()) {
R[i] = n + 1;
} else {
R[i] = it->second;
}
mp[p[i]] = i;
to = std::min(to, R[i]);
parent[i] = to;
depth[i] = depth[parent[i]] + 1;
if (depth[parent[i]] - depth[jump[parent[i]]] == depth[jump[parent[i]]] - depth[jump[jump[parent[i]]]]) {
jump[i] = jump[jump[parent[i]]];
} else {
jump[i] = parent[i];
}
}
dbg(p);
dbg(R);
dbg(jump);
dbg(depth);
dbg(parent);
int Q;
std::cin >> Q;
while (Q--) {
int l, r;
std::cin >> l >> r;
l--;
int counter = 0;
int u = l;
while (parent[u] <= r) {
if (jump[u] <= r) {
counter += depth[u] - depth[jump[u]];
u = jump[u];
} else {
counter++;
u = parent[u];
}
}
std::cout << counter << nl;
}
}