| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 794676 |
2023-07-26T18:58:12 Z |
eltu0815 |
Fish 2 (JOI22_fish2) |
C++14 |
|
289 ms |
92056 KB |
#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);
}
int 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 && l[a][b] < 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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
289 ms |
92056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
289 ms |
92056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
289 ms |
92056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
