oj.uz

Submission #794651

# Submission time Handle Problem Language Result Execution time Memory
794651 2023-07-26T18:23:56 Z eltu0815 Fish 2 (JOI22_fish2) C++14
8 / 100
 220 ms 61132 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 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, mx = 0; i <= n; ++i) {
        L[i][0] = i;
        for(int j = 1, x = arr[i]; x < mx; x <<= 1, ++j) L[i][j] = query2(1, n, x, 1);
        update(1, n, i, arr[i], 1); mx = max(mx, arr[i]);
    }
    fill(seg + 1, seg + 4 * n + 1, 0);
    for(int i = n, mx = 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 < mx; x <<= 1, ++j) R[i][j] = query1(1, n, x, 1);
        update(1, n, i, arr[i], 1); mx = max(mx, 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]);
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        int a = i, b = n;
        for(int j = 0; j <= 30; ++j) {
            if(R[i][j] != n + 1 && b > l[i][j]) b = l[i][j];
            if(r[i][j] != n + 1 && a > L[i][j + 1]) a = L[i][j + 1];
        }
        if(a < 1 && 1 <= b) ++ans;
    }
    cout << ans;
    
//    for(int i = 1; i <= n; ++i) {
//        cout << "r : " << i << endl;
//        for(auto p : event[i]) cout << p.first.first << ' ' << p.first.second << ' ' << p.second << endl;
//        cout << endl;
//    }
//    
//    cin >> q;
//    for(int i = 1; i <= q; ++i) {
//        cin >> query[i].l >> query[i].r;
//        query[i].i = i;
//    }
//    sort(query + 1, query + q + 1);
    
    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 'int main()':
fish2.cpp:82:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
fish2.cpp:97:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |                 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 1 ms 2644 KB Output is correct
2 Correct 131 ms 60160 KB Output is correct
3 Correct 173 ms 60116 KB Output is correct
4 Correct 161 ms 60108 KB Output is correct
5 Correct 169 ms 60180 KB Output is correct
6 Correct 82 ms 60168 KB Output is correct
7 Correct 215 ms 60480 KB Output is correct
8 Correct 81 ms 61132 KB Output is correct
9 Correct 220 ms 60296 KB Output is correct
10 Correct 149 ms 60776 KB Output is correct
11 Correct 179 ms 60444 KB Output is correct
12 Correct 141 ms 60392 KB Output is correct
13 Correct 148 ms 60448 KB Output is correct
14 Correct 129 ms 60776 KB Output is correct
15 Correct 127 ms 60704 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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 131 ms 60160 KB Output is correct
3 Correct 173 ms 60116 KB Output is correct
4 Correct 161 ms 60108 KB Output is correct
5 Correct 169 ms 60180 KB Output is correct
6 Correct 82 ms 60168 KB Output is correct
7 Correct 215 ms 60480 KB Output is correct
8 Correct 81 ms 61132 KB Output is correct
9 Correct 220 ms 60296 KB Output is correct
10 Correct 149 ms 60776 KB Output is correct
11 Correct 179 ms 60444 KB Output is correct
12 Correct 141 ms 60392 KB Output is correct
13 Correct 148 ms 60448 KB Output is correct
14 Correct 129 ms 60776 KB Output is correct
15 Correct 127 ms 60704 KB Output is correct
16 Incorrect 1 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 131 ms 60160 KB Output is correct
3 Correct 173 ms 60116 KB Output is correct
4 Correct 161 ms 60108 KB Output is correct
5 Correct 169 ms 60180 KB Output is correct
6 Correct 82 ms 60168 KB Output is correct
7 Correct 215 ms 60480 KB Output is correct
8 Correct 81 ms 61132 KB Output is correct
9 Correct 220 ms 60296 KB Output is correct
10 Correct 149 ms 60776 KB Output is correct
11 Correct 179 ms 60444 KB Output is correct
12 Correct 141 ms 60392 KB Output is correct
13 Correct 148 ms 60448 KB Output is correct
14 Correct 129 ms 60776 KB Output is correct
15 Correct 127 ms 60704 KB Output is correct
16 Incorrect 2 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 -