oj.uz

Submission #791123

# Submission time Handle Problem Language Result Execution time Memory
791123 2023-07-23T12:35:43 Z eltu0815 Fish 2 (JOI22_fish2) C++14
8 / 100
 159 ms 27464 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) {
            ll tmp = sum[mn[i][j] - 1] - sum[mx[i][j]];
            if(arr[mn[i][j]] == 0 && arr[mx[i][j]] == 0) break;
            else if(arr[mn[i][j]] == 0 && tmp < arr[mx[i][j]]) flag = 0;
            else if(arr[mx[i][j]] == 0 && tmp < arr[mn[i][j]]) flag = 0;
            else if(arr[mn[i][j]] && arr[mx[i][j]] && tmp < min(arr[mx[i][j]], arr[mn[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 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 107 ms 26492 KB Output is correct
3 Correct 144 ms 26812 KB Output is correct
4 Correct 107 ms 27084 KB Output is correct
5 Correct 152 ms 26784 KB Output is correct
6 Correct 55 ms 27412 KB Output is correct
7 Correct 156 ms 26760 KB Output is correct
8 Correct 55 ms 27464 KB Output is correct
9 Correct 146 ms 26720 KB Output is correct
10 Correct 116 ms 27104 KB Output is correct
11 Correct 159 ms 26712 KB Output is correct
12 Correct 125 ms 26692 KB Output is correct
13 Correct 122 ms 26656 KB Output is correct
14 Correct 106 ms 27084 KB Output is correct
15 Correct 102 ms 27064 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 Correct 107 ms 26492 KB Output is correct
3 Correct 144 ms 26812 KB Output is correct
4 Correct 107 ms 27084 KB Output is correct
5 Correct 152 ms 26784 KB Output is correct
6 Correct 55 ms 27412 KB Output is correct
7 Correct 156 ms 26760 KB Output is correct
8 Correct 55 ms 27464 KB Output is correct
9 Correct 146 ms 26720 KB Output is correct
10 Correct 116 ms 27104 KB Output is correct
11 Correct 159 ms 26712 KB Output is correct
12 Correct 125 ms 26692 KB Output is correct
13 Correct 122 ms 26656 KB Output is correct
14 Correct 106 ms 27084 KB Output is correct
15 Correct 102 ms 27064 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 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 Correct 107 ms 26492 KB Output is correct
3 Correct 144 ms 26812 KB Output is correct
4 Correct 107 ms 27084 KB Output is correct
5 Correct 152 ms 26784 KB Output is correct
6 Correct 55 ms 27412 KB Output is correct
7 Correct 156 ms 26760 KB Output is correct
8 Correct 55 ms 27464 KB Output is correct
9 Correct 146 ms 26720 KB Output is correct
10 Correct 116 ms 27104 KB Output is correct
11 Correct 159 ms 26712 KB Output is correct
12 Correct 125 ms 26692 KB Output is correct
13 Correct 122 ms 26656 KB Output is correct
14 Correct 106 ms 27084 KB Output is correct
15 Correct 102 ms 27064 KB Output is correct
16 Incorrect 0 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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