제출 #401967

#제출 시각아이디문제언어결과실행 시간메모리
401967maximath_1Sum Zero (RMI20_sumzero)C++11
61 / 100
547 ms23440 KiB
#include <iostream> #include <math.h> #include <iomanip> #include <vector> #include <algorithm> #include <assert.h> #include <set> #include <functional> #include <limits.h> #include <map> #include <queue> using namespace std; #define ll long long #define ld long double #define endl "\n" const int MX = 400005; const int BLOCK = 350; const ll mod = 998244353; const int LG = 5; int n, q; map<ll, int> last; ll v[MX]; int anc[MX][LG], pw10[LG + 1]; int main(){ pw10[0] = 1; for(int i = 1; i <= LG; i ++) pw10[i] = pw10[i - 1] * 10; cin.tie(0) -> sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i ++) cin >> v[i]; for(int i = 1; i <= n; i ++) v[i] += v[i - 1]; last[v[n]] = n; anc[n][0] = n + 1; for(int i = n - 1; i >= 0; i --){ if(!last.count(v[i])) anc[i][0] = n + 1; else anc[i][0] = last[v[i]]; last[v[i]] = i; } for(int i = n - 1; i >= 0; i --) anc[i][0] = min(anc[i][0], anc[i + 1][0]); for(int j = 1; j < LG; j ++){ for(int i = 0; i <= n; i ++){ if(anc[i][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[i][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[i][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1; else anc[i][j] = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]; } } cin >> q; for(int l, r, i = 0; i < q; i ++){ cin >> l >> r; l --; int ans = 0, nw = l; for(int j = LG; j >= 0; j --){ for(int tp = 0; tp < 10; tp ++){ if(j == LG){ int cr; if(anc[nw][j - 1] == n + 1) cr = n + 1; else if(anc[anc[nw][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[nw][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1; else cr = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]; if(cr <= r){ ans += pw10[j]; nw = cr; } }else{ if(anc[nw][j] <= r){ ans += pw10[j]; nw = anc[nw][j]; }else break; } } } cout << ans << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...