oj.uz

Submission #794684

# Submission time Handle Problem Language Result Execution time Memory
794684 2023-07-26T19:02:06 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 546 ms 116624 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[400005], lazy[400005];
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

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;
      |                           ~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 285 ms 93336 KB Output is correct
3 Correct 339 ms 108072 KB Output is correct
4 Correct 295 ms 92856 KB Output is correct
5 Correct 347 ms 107208 KB Output is correct
6 Correct 191 ms 71240 KB Output is correct
7 Correct 488 ms 114280 KB Output is correct
8 Correct 190 ms 71244 KB Output is correct
9 Correct 478 ms 110916 KB Output is correct
10 Correct 292 ms 91796 KB Output is correct
11 Correct 342 ms 106820 KB Output is correct
12 Correct 314 ms 94944 KB Output is correct
13 Correct 325 ms 100432 KB Output is correct
14 Correct 273 ms 91812 KB Output is correct
15 Correct 279 ms 91392 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 285 ms 93336 KB Output is correct
3 Correct 339 ms 108072 KB Output is correct
4 Correct 295 ms 92856 KB Output is correct
5 Correct 347 ms 107208 KB Output is correct
6 Correct 191 ms 71240 KB Output is correct
7 Correct 488 ms 114280 KB Output is correct
8 Correct 190 ms 71244 KB Output is correct
9 Correct 478 ms 110916 KB Output is correct
10 Correct 292 ms 91796 KB Output is correct
11 Correct 342 ms 106820 KB Output is correct
12 Correct 314 ms 94944 KB Output is correct
13 Correct 325 ms 100432 KB Output is correct
14 Correct 273 ms 91812 KB Output is correct
15 Correct 279 ms 91392 KB Output is correct
16 Correct 1 ms 2644 KB Output is correct
17 Correct 386 ms 110720 KB Output is correct
18 Correct 319 ms 94132 KB Output is correct
19 Correct 384 ms 110312 KB Output is correct
20 Correct 384 ms 111344 KB Output is correct
21 Correct 389 ms 111372 KB Output is correct
22 Correct 318 ms 94076 KB Output is correct
23 Correct 381 ms 110704 KB Output is correct
24 Correct 379 ms 110796 KB Output is correct
25 Correct 389 ms 110480 KB Output is correct
26 Correct 390 ms 110796 KB Output is correct
27 Correct 237 ms 75648 KB Output is correct
28 Correct 237 ms 75728 KB Output is correct
29 Correct 234 ms 75700 KB Output is correct
30 Correct 532 ms 112836 KB Output is correct
31 Correct 546 ms 116624 KB Output is correct
32 Correct 395 ms 109820 KB Output is correct
33 Correct 352 ms 96748 KB Output is correct
34 Correct 387 ms 110392 KB Output is correct
35 Correct 399 ms 111988 KB Output is correct
36 Correct 325 ms 96892 KB Output is correct
37 Correct 384 ms 101612 KB Output is correct
38 Correct 348 ms 95448 KB Output is correct
39 Correct 384 ms 95824 KB Output is correct
40 Correct 317 ms 95260 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 285 ms 93336 KB Output is correct
3 Correct 339 ms 108072 KB Output is correct
4 Correct 295 ms 92856 KB Output is correct
5 Correct 347 ms 107208 KB Output is correct
6 Correct 191 ms 71240 KB Output is correct
7 Correct 488 ms 114280 KB Output is correct
8 Correct 190 ms 71244 KB Output is correct
9 Correct 478 ms 110916 KB Output is correct
10 Correct 292 ms 91796 KB Output is correct
11 Correct 342 ms 106820 KB Output is correct
12 Correct 314 ms 94944 KB Output is correct
13 Correct 325 ms 100432 KB Output is correct
14 Correct 273 ms 91812 KB Output is correct
15 Correct 279 ms 91392 KB Output is correct
16 Incorrect 1 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -