oj.uz

Submission #791111

# Submission time Handle Problem Language Result Execution time Memory
791111 2023-07-23T12:29:03 Z eltu0815 Fish 2 (JOI22_fish2) C++14
0 / 100
 114 ms 26500 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 mx[100005][30], mn[100005][30];
int arr[100005], seg[400005];
ll 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

fish2.cpp: In function 'void update(int, int, int, int, int)':
fish2.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query1(int, int, int, int)':
fish2.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
fish2.cpp: In function 'int query2(int, int, int, int)':
fish2.cpp:37:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 114 ms 26500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 114 ms 26500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 114 ms 26500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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