Submission #794680

#TimeUsernameProblemLanguageResultExecution timeMemory
794680eltu0815Fish 2 (JOI22_fish2)C++14
0 / 100
281 ms92840 KiB
#include <bits/stdc++.h> #define MAX 500005 #define MOD (ll)(1e9+7) #define INF (ll)(1e18) #define inf (1987654321) using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; int n, q; int arr[100005], ans[100005]; int L[100005][35], R[100005][35]; int l[100005][35], r[100005][35]; ll sum[100005]; vector<pair<pii, int> > event[100005]; struct INFO { int l, r, i; bool operator < (INFO q) { if(r != q.r) return r < q.r; else return pii(l, i) < pii(q.l, q.i); } } query[100005]; int seg[400005]; void update(int str, int ed, int idx, int val, int node) { if(str == ed) { seg[node] = val; return; } int mid = str + ed >> 1; if(idx <= mid) update(str, mid, idx, val, node << 1); else update(mid + 1, ed, idx, val, node << 1 | 1); seg[node] = max(seg[node << 1], seg[node << 1 | 1]); } int query1(int str, int ed, int x, int node) { if(str == ed) return str; int mid = str + ed >> 1; if(seg[node << 1] > x) return query1(str, mid, x, node << 1); else return query1(mid + 1, ed, x, node << 1 | 1); } int query2(int str, int ed, int x, int node) { if(str == ed) return str; int mid = str + ed >> 1; if(seg[node << 1 | 1] > x) return query2(mid + 1, ed, x, node << 1 | 1); else return query2(str, mid, x, node << 1); } ll seg2[100005], lazy[100005]; int mn[100005], mx[100005]; void lazyProp(int str, int ed, int node) { if(lazy[node]) { seg2[node] += (ed - str + 1) * lazy[node]; if(str != ed) { lazy[node << 1] += lazy[node]; lazy[node << 1 | 1] += lazy[node]; } lazy[node] = 0; } } void update2(int str, int ed, int left, int right, int val, int node) { lazyProp(str, ed, node); if(str > right || ed < left) return; if(left <= str && ed <= right) { lazy[node] += val; lazyProp(str, ed, node); return; } int mid = str + ed >> 1; update2(str, mid, left, right, val, node << 1); update2(mid + 1, ed, left, right, val, node << 1 | 1); seg2[node] = seg2[node << 1] + seg2[node << 1 | 1]; } int query3(int str, int ed, int idx, int node) { lazyProp(str, ed, node); if(str == ed) return seg2[node]; int mid = str + ed >> 1; if(idx <= mid) return query3(str, mid, idx, node << 1); else return query3(mid + 1, ed, idx, node << 1 | 1); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 1; i <= n; ++i) cin >> arr[i]; for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + arr[i]; for(int i = 1, mxv = 0; i <= n; ++i) { L[i][0] = i; for(int j = 1, x = arr[i]; x < mxv; x <<= 1, ++j) L[i][j] = query2(1, n, x, 1); update(1, n, i, arr[i], 1); mxv = max(mxv, arr[i]); } fill(seg + 1, seg + 4 * n + 1, 0); for(int i = n, mxv = 0; i >= 1; --i) { R[i][0] = i; for(int j = 1; j <= 30; ++j) R[i][j] = n + 1; for(int j = 1, x = arr[i]; x < mxv; x <<= 1, ++j) R[i][j] = query1(1, n, x, 1); update(1, n, i, arr[i], 1); mxv = max(mxv, arr[i]); } arr[0] = arr[n + 1] = inf; for(int i = 1; i <= n; ++i) { l[i][0] = i; for(int j = 1; j <= 30; ++j) { if(R[i][j] == n + 1 || sum[R[i][j] - 1] - sum[L[i][j]] < (ll)min(arr[L[i][j]], arr[R[i][j]])) break; int lo = 1, hi = i + 1; while(lo + 1 < hi) { int mid = lo + hi >> 1; if(sum[R[i][j] - 1] - sum[mid - 1] >= arr[R[i][j]]) lo = mid; else hi = mid; } l[i][j] = min(lo, l[i][j - 1]); } } for(int i = 1; i <= n; ++i) { r[i][0] = i; for(int j = 1; j <= 30; ++j) r[i][j] = n + 1; for(int j = 1; j <= 30; ++j) { if(L[i][j] == 0 || sum[R[i][j] - 1] - sum[L[i][j]] < (ll)min(arr[L[i][j]], arr[R[i][j]])) break; int lo = i - 1, hi = n; while(lo + 1 < hi) { int mid = lo + hi >> 1; if(sum[mid] - sum[L[i][j]] >= arr[L[i][j]]) hi = mid; else lo = mid; } r[i][j] = max(hi, r[i][j - 1]); } } for(int i = 1; i <= n; ++i) { for(int j = 0; j <= 30; ++j) { if(R[i][j] != n + 1) event[R[i][j]].push_back({{i, j}, 0}); if(r[i][j] != n + 1) event[r[i][j]].push_back({{i, j}, 1}); } } for(int i = 1; i <= n; ++i) { update2(1, n, i, n, 1, 1); mn[i] = i - 1, mx[i] = n; } cin >> q; for(int i = 1; i <= q; ++i) { int t; cin >> t >> query[i].l >> query[i].r; query[i].i = i; } sort(query + 1, query + q + 1); for(int i = 1, j = 1; i <= n; ++i) { for(auto p : event[i]) { int a = p.first.first, b = p.first.second; if(p.second == 0 && max(l[a][b], mn[a]) < mx[a]) { update2(1, n, l[a][b] + 1, mx[a], -1, 1); mx[a] = l[a][b]; } if(p.second == 1 && L[a][b + 1] < mn[a]) { update2(1, n, L[a][b + 1] + 1, mn[a], 1, 1); mn[a] = L[a][b + 1]; } if(mx[a] < mn[a]) { update2(1, n, mx[a] + 1, mn[a], 1, 1); mx[a] = mn[a] = 0; } } while(j <= q && query[j].r == i) { ans[query[j].i] = query3(1, n, query[j].l, 1); ++j; } } for(int i = 1; i <= q; ++i) cout << ans[i] << '\n'; return 0; }

Compilation message (stderr)

fish2.cpp: In function 'void update(int, int, int, int, int)':
fish2.cpp:33:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query1(int, int, int, int)':
fish2.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query2(int, int, int, int)':
fish2.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'void update2(int, int, int, int, int, int)':
fish2.cpp:74:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query3(int, int, int, int)':
fish2.cpp:83:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int main()':
fish2.cpp:117:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
fish2.cpp:132:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...