# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
942912 | 2024-03-11T06:53:12 Z | vjudge1 | Nicelines (RMI20_nicelines) | C++17 | 0 ms | 0 KB |
#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; } }