Submission #791110

#TimeUsernameProblemLanguageResultExecution timeMemory
791110eltu0815Fish 2 (JOI22_fish2)C++14
0 / 100
127 ms26680 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 mx[100005][30], mn[100005][30]; int arr[100005], seg[400005], sum[100005]; 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); } 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) { for(int j = 0, x = arr[i]; x <= mxv; x <<= 1, ++j) mx[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) { for(int j = 0; j < 30; ++j) mn[i][j] = n + 1; for(int j = 0, x = arr[i]; x <= mxv; x <<= 1, ++j) mn[i][j] = query1(1, n, x, 1); update(1, n, i, arr[i], 1); mxv = max(mxv, arr[i]); } int cnt = 0; for(int i = 1; i <= n; ++i) { int flag = 1; for(int j = 0; j < 30; ++j) { int tmp = sum[mn[i][j] - 1] - sum[mx[i][j]]; if(tmp < min(arr[mn[i][j]], arr[mx[i][j]])) flag = 0; } cnt += flag; } cout << cnt; return 0; }

Compilation message (stderr)

fish2.cpp: In function 'void update(int, int, int, int, int)':
fish2.cpp:21:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query1(int, int, int, int)':
fish2.cpp:29:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query2(int, int, int, int)':
fish2.cpp:36:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = str + ed >> 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...