제출 #753342

#제출 시각아이디문제언어결과실행 시간메모리
753342lukameladzeSum Zero (RMI20_sumzero)C++14
22 / 100
134 ms33780 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define int long long #define pii pair <int, int> #define pb push_back const int N = 3e5 + 5, inf = 1e9; int t, n, a[N],par[N][21],pr[N],nxt[N]; map <int, int> mp; int tree[N]; vector <int> vec[N]; void upd(int idx, int val) { for (int i = idx; i > 0; i -= i&(-i)) tree[i] = min(tree[i], val); } int getmn(int idx) { // suffix query int pas = n + 1; for (int i = idx; i < N; i += i&(-i)) pas = min(pas, tree[i]); return pas; } main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for (int i = 1; i <= n; i++) { cin>>a[i]; pr[i] = pr[i - 1] + a[i]; nxt[i] = -1; } mp[pr[0]] = 0; for (int i = 1; i <= n; i++) { if (mp[pr[i]] != 0 || pr[i] == 0) { vec[mp[pr[i]] + 1].pb(i); nxt[mp[pr[i]] + 1] = i; } mp[pr[i]] = i; } int mn = inf; vector <pii> v; for (int i = n; i >= 1; i--) { if (nxt[i] == -1) continue; if (mn <= nxt[i]) continue; v.pb({i, nxt[i]}); mn = min(mn, nxt[i]); } sort(v.begin(), v.end()); // if (l[i] > l[j]) ---> r[i] > r[j] int m = v.size(); for (int i = 1; i < N; i++) tree[i] = n + 1; for (int i = (int)v.size() - 1; i >= 0; i--) { par[i + 1][0] = getmn(v[i].s + 1); upd(v[i].f, i + 1); } for (int j = 1; j <= 20; j++) { for (int i = 1; i <= n; i++) { if (par[i][j - 1] == n + 1) par[i][j] = n + 1; else par[i][j] = par[par[i][j - 1]][j - 1]; } } for (int i = 0; i < v.size(); i++) { //cout<<v[i].f<<" --> "<<v[i].s<<"\n"; } int q; cin>>q; while (q--) { int le, ri; cin>>le>>ri; int st_idx = getmn(le); if (st_idx == n + 1 || v[st_idx - 1].f > ri) { cout<<0<<"\n"; continue; } int cur = st_idx; int ans = 0; for (int i = 20; i >= 0; i--) { if (par[cur][i] != n + 1 && v[par[cur][i] - 1].f <= ri) cur = par[cur][i], ans += (1<<i); } if (v[cur - 1].s <= ri) ans++; cout<<ans<<"\n"; } }

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~
sumzero.cpp: In function 'int main()':
sumzero.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
sumzero.cpp:46:9: warning: unused variable 'm' [-Wunused-variable]
   46 |     int m = v.size();
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...