# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
961600 | 2024-04-12T08:44:56 Z | thangdz2k7 | Sum Zero (RMI20_sumzero) | C++17 | 9 ms | 22360 KB |
// author : HuuHung // 25.3.2024 #include <bits/stdc++.h> #define ll long long #define pb push_back using namespace std; const int N = 4e5 + 5; // * end int n, q; map <ll, int> mp; vector <int> adj[N], ev[N]; int l[N], ans[N]; vector <int> dhs; void dfs(int u){ dhs.pb(u); for (int i : ev[u]){ int L = 0; int R = dhs.size() - 1; while (L <= R){ int mid = L + R >> 1; if (dhs[mid] >= l[i]){ ans[i] = mid; R = mid - 1; } else L = mid + 1; } ans[i] = dhs.size() - ans[i]; } for (int v : adj[u]) dfs(v); dhs.pop_back(); } void solve(){ cin >> n; mp[0] = 1; ll sum = 0; int nxt = -1; adj[0].pb(1); for (int i = 1; i <= n; ++ i){ int c; cin >> c; sum += c; nxt = max(nxt, mp[sum] - 1); adj[nxt + 1].pb(i + 1); //cout << nxt[i] << endl; mp[sum] = i + 1; } cin >> q; for (int i = 1; i <= q; ++ i){ int r; cin >> l[i] >> r; ++ r; ev[r].pb(i); } dfs(0); for (int i = 1; i <= q; ++ i) cout << ans[i] - 1 << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; while (t --) solve(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 9 ms | 22360 KB | Memory limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 9 ms | 22360 KB | Memory limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 9 ms | 22360 KB | Memory limit exceeded |
2 | Halted | 0 ms | 0 KB | - |