Submission #794651

#	Time	Username	Problem	Language	Result	Execution time	Memory
794651		eltu0815	Fish 2 (JOI22_fish2)	C++14	8 / 100	220 ms	61132 KiB

fish2

#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 (stderr)

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
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17