Submission #710047

#	Time	Username	Problem	Language	Result	Execution time	Memory
710047		Paul_Liao_1457	Fish 2 (JOI22_fish2)	C++17	13 / 100	222 ms	4044 KiB

fish2

//記得跳題
#pragma GCC optimize("O3,unroll_loops")
#pragma GCC target("avx2")
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
#include<random>

using namespace std;

#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define INF (ll)(4e18)
#define pb push_back
#define mp make_pair
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"

ll a[100005];
int t[100005], x[100005], y[100005], n, q;

void sub1() {
    FOR(i, 0, q) {
        if (t[i] == 1) {
            a[x[i]] = y[i];
        } else {
            int ans = 0;
            ll inia = a[x[i] - 1], inib = a[y[i] + 1];
            a[x[i] - 1] = a[y[i] + 1] = INF;
            
            ll maxn = 0;
            
            FOR(j, x[i], y[i] + 1) {
                maxn = max(maxn, a[j]);
            }
            
            FOR(j, x[i], y[i] + 1) {
                int l = j - 1, r = j + 1;
                ll now = a[j];
                while (1) {
                    if (a[l] > now && a[r] > now) break;
                    if (a[l] <= now) {
                        now += a[l]; l--;
                    }
                    if (a[r] <= now) {
                        now += a[r]; r++;
                    }
                }
                if (now >= maxn) {
                    ans++;
                }
            }
            cout << ans << endl;
            a[x[i] - 1] = inia;
            a[y[i] + 1] = inib;
        }
    }
}

ll maxn[400005];

void build(int id, int l, int r) {
    if (l == r) {
        maxn[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    maxn[id] = max(maxn[id << 1], maxn[id << 1 | 1]);
}

int ask(int id, int l, int r, int L, int R, ll x, int t) {
    if (maxn[id] < x) return (t ? n + 1 : 0);
    if (l > R || r < L) {
        return (t ? n + 1 : 0);
    }
    if (l == r) return l;
    if (L <= l && r <= R) {
        int mid = (l + r) >> 1;
        if (t) {
            if (maxn[id << 1] <= x) {
                return ask(id << 1 | 1, mid + 1, r, L, R, x, t);
            } else {
                return ask(id << 1, l, mid, L, R, x, t);
            }
        } else {
            if (maxn[id << 1 | 1] <= x) {
                return ask(id << 1, l, mid, L, R, x, t);
            } else {
                return ask(id << 1 | 1, mid + 1, r, L, R, x, t);
            }
        }
    }
    int mid = (l + r) >> 1;
    if (t) return min(ask(id << 1, l, mid, L, R, x, t), ask(id << 1 | 1, mid + 1, r, L, R, x, t));
    else return max(ask(id << 1, l, mid, L, R, x, t), ask(id << 1 | 1, mid + 1, r, L, R, x, t));
}

ll pre[100005];

void sub2() {
    build(1, 1, n);
    
    ll maxn = 0, ans = 0;
    FOR(i, 1, n+1) {
        maxn = max(maxn, a[i]);
        pre[i] = pre[i-1] + a[i];
    }
    pre[n+1] = pre[n];
    
    FOR(i, 1, n+1) {
        int l = i - 1, r = i + 1;
        ll now = a[i];
        while (1) {
            int nl = ask(1, 1, n, 1, l ,now, 0), nr = ask(1, 1, n, r, n, now, 1);
            now += pre[l] - pre[nl];
            now += pre[nr - 1] - pre[r - 1];
            
            if (now >= maxn) {
                ans++;
                break;
            }
            
            if (now < a[nl] && now < a[nr]) break;
            
            if (a[nl] <= a[nr]) {
                if (now >= a[nl]) {
                    now += a[nl];
                    l = nl - 1;
                    l = max(0, l);
                } else {
                    l = nl;
                }
                
                if (now >= a[nr]) {
                    now += a[nr];
                    r = nr + 1;
                    r = min(n+1, r);
                } else {
                    r = nr;
                }
            } else {
                
                if (now >= a[nr]) {
                    now += a[nr];
                    r = nr + 1;
                    r = min(n+1, r);
                } else {
                    r = nr;
                }
                
                if (now >= a[nl]) {
                    now += a[nl];
                    l = nl - 1;
                    l = max(0, l);
                } else {
                    l = nl;
                }
            }
        }
        //cout << "now = " << now << endl;
    }
    
    cout << ans << endl;
}

signed main() {
    AC;
    // plz
    
    cin >> n;
    FOR(i, 1, n+1) cin >> a[i];
    cin >> q;
    FOR(i, 0, q) cin >> t[i] >> x[i] >> y[i];
    
    a[0] = a[n+1] = INF;
    
    if (n <= 500 && q <= 500) {
        sub1();
    } else if (q == 1) {
        sub2();
    }
}

Compilation message (stderr)

fish2.cpp:2:39: warning: bad option '-funroll_loops' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("O3,unroll_loops")
      |                                       ^
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
    3 | #pragma GCC target("avx2")
      |                          ^
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17