제출 #942640

#제출 시각아이디문제언어결과실행 시간메모리
942640Tuanlinh123Sum Zero (RMI20_sumzero)C++17
0 / 100
10 ms27380 KiB
#include<bits/stdc++.h> #define ll int #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=400005; long long pre[maxn]; vector <pll> Q[maxn]; vector <ll> crr, A[maxn]; ll a[maxn], to[maxn], last[maxn], ans[maxn]; void dfs(ll u, ll pa) { for (auto [r, id]:Q[u]) ans[id]=crr.end()-lower_bound(crr.begin(), crr.end(), r, greater<ll>()); crr.pb(u); for (ll v:A[u]) if (v!=pa) dfs(v, u); crr.pop_back(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; vector <long long> num; num.pb(0); for (ll i=1; i<=n; i++) cin >> a[i], pre[i]=pre[i-1]+a[i], num.pb(pre[i]); sort(num.begin(), num.end()); num.resize(unique(num.begin(), num.end())-num.begin()); for (ll i=0; i<=n+1; i++) to[i]=n+2, last[i]=-1; for (ll i=0; i<=n; i++) { pre[i]=lower_bound(num.begin(), num.end(), pre[i])-num.begin(); if (last[pre[i]]!=-1) to[last[pre[i]]]=i+1; last[pre[i]]=i+1; } for (ll i=n; i>=1; i--) to[i]=min(to[i], to[i+1]); for (ll i=1; i<=n+1; i++) A[to[i]].pb(i); ll q; cin >> q; for (ll i=1; i<=q; i++) { ll l, r; cin >> l >> r; Q[l].pb({r+1, i}); } dfs(n+2, n+2); for (ll i=1; i<=q; i++) cout << ans[i] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...