제출 #1112658

#제출 시각아이디문제언어결과실행 시간메모리
1112658IcelastSum Zero (RMI20_sumzero)C++17
61 / 100
591 ms26548 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define ll long long template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;} template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;} const int N = 4e5 + 1, LG = 5, mod = 1e9 + 7; const ll INF = 1e18; int up[N][LG]; map <ll, int> pos; int n, m, Q; struct creature{ int x, v; }; creature a[N]; void inp(){ cin >> n; m = 0; for(int i = 1; i <= n; i++){ cin >> a[i].v; a[i].x = i; } for(int i = n+1; i <= n+m; i++){ cin >> a[i].x >> a[i].v; a[i].v*=-1; } cin >> Q; } bool cmp(creature a, creature b){ return a.x < b.x; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); inp(); vector<ll> v; sort(a+1, a+1+n, cmp); for(int i = 1; i <= N; i++){ v.push_back(i); //cout << a[i].v << " "; } for (int j = 0; j < LG; j++) for (int i = 0; i <= n; i++) up[i][j] = n + 1; pos[0] = 0; ll sum = 0; for (int i = 1; i <= n; i++) { sum += a[i].v; if (pos.count(sum)) up[pos[sum]][0] = i; pos[sum] = i; } for (int i = n - 1; i >= 0; i--) minimize(up[i][0], up[i + 1][0]); for (int j = 1; j < LG; j++) for (int i = 0; i <= n; i++) { int pos = i; for (int times = 0; times < 16; times++) if (pos <= n) pos = up[pos][j - 1]; up[i][j] = pos; } int x, y; while(Q--){ cin >> x >> y; int l = lower_bound(v.begin(), v.end(), x) - v.begin()+1, r = upper_bound(v.begin(), v.end(), y)-v.begin(); int pos = l - 1, ans = 0, k = LG - 1; while (k >= 0) { if (up[pos][k] <= r) pos = up[pos][k], ans += (1 << (4 * k)); else k--; } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...