제출 #950164

#제출 시각아이디문제언어결과실행 시간메모리
950164TrieTrSum Zero (RMI20_sumzero)C++14
0 / 100
5 ms9304 KiB
#include<bits/stdc++.h> using namespace std; void local() { #define taskname "" if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } } #define ll long long #define fi first #define se second #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;} template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;} const int N = 4e5 + 5; const int LG = 19; int n, q; int arr[N]; map<ll, int> pos; int nxt[N]; int depth[N]; bool vis[N]; int node_id[N], par[N], h[N], jump[N], cur_pos[N]; void make_leaf(int id, int p) { par[id] = p; h[id] = h[p] + 1; if(h[jump[p]] - h[p] == h[jump[jump[p]]] - h[jump[p]]) jump[id] = jump[jump[p]]; else jump[id] = p; } int main() { fastio; local(); cin >> n; for(int i = 1; i <= n; i++) cin >> arr[i]; ll sum = 0; nxt[n + 1] = n + 1; pos[0] = n + 1; for(int i = n; i > 0; i--) { sum += arr[i]; nxt[i] = pos[sum] - 1; if(nxt[i] == -1) nxt[i] = nxt[i + 1]; else mini(nxt[i], nxt[i + 1]); pos[sum] = i; } cur_pos[0] = n + 1; for(int i = n - 1, id = 0; i > 0; i--) { int u = nxt[i]; if(vis[u] || u > n) continue; vis[u] = true; id++; int p = node_id[nxt[u + 1]]; make_leaf(id, p); node_id[u] = id; cur_pos[id] = u; } /*for(int i = 1; i <= n; i++) { int id = node_id[i]; cout << i << ' ' << id << ' ' << par[id] << ' ' << h[id] << ' ' << jump[id] << ' ' << cur_pos[id] << '\n'; }*/ cin >> q; while(q--) { int l, r; cin >> l >> r; l = nxt[l]; int res = 0, id; if(l <= r) id = node_id[l]; int cnt = 0; while(cur_pos[id] <= r) { int tmp = id; if(cur_pos[jump[id]] <= r) { res += h[id] - h[jump[id]]; id = jump[id]; } else { res++; id = par[id]; } //cout << tmp << ' ' << id << ' ' << h[tmp] << ' ' << h[id] << ' ' << res << '\n'; //cnt++; if(cnt > 3) break; } cout << res << '\n'; } }

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

sumzero.cpp: In function 'int main()':
sumzero.cpp:72:8: warning: unused variable 'tmp' [-Wunused-variable]
   72 |    int tmp = id;
      |        ^~~
sumzero.cpp:70:7: warning: unused variable 'cnt' [-Wunused-variable]
   70 |   int cnt = 0;
      |       ^~~
sumzero.cpp: In function 'void local()':
sumzero.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp: In function 'int main()':
sumzero.cpp:71:19: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |   while(cur_pos[id] <= r) {
      |         ~~~~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...