Submission #1081475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081475		Evirir	Fish 2 (JOI22_fish2)	C++17	13 / 100	4090 ms	7916 KiB

fish2

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;

int n,Q;
vector<ll> a;

struct DSU {
    struct Node {
        int p, sz;
        int alive;
        ll sum = 0;
    };
    vector<Node> comp;
    int cc;
    Node& operator[](int id) { return comp[rt(id)]; }
    DSU(int n = 0) {
        comp.resize(n); cc = n;
        forn(i, 0, n) { comp[i] = {i, 1, 1, a[i]}; }
    }
    inline int rt(int u) { return (comp[u].p == u) ? u : comp[u].p = rt(comp[u].p); }
    inline bool sameset(int u, int v) { return rt(u) == rt(v); }
    void merge(int u0, int v0) {
        int u = rt(u0); int v = rt(v0);
        if (u == v) return;
        int eaten = v, eater = u;
        if (comp[u].sz < comp[v].sz) swap(u, v);
        comp[v].p = u;
        comp[u].sz += comp[v].sz;
        if (comp[eaten].sum >= a[u0])
            comp[u].alive += comp[v].alive; // vore uwu
        else
            comp[u].alive = comp[eater].alive;
        comp[u].sum += comp[v].sum;
        cc--;
    }
};


int query(int l, int r)
{
    vector<ii> vp;
    fore(i,l,r) vp.pb({a[i], i});
    sort(all(vp));

    DSU dsu(n);
    for (const auto& [val, p] : vp)
    {
        if (p - 1 >= l && a[p] >= a[p - 1]) dsu.merge(p, p - 1);
        if (p + 1 <= r && a[p] >= a[p + 1]) dsu.merge(p, p + 1);
    }
    return dsu[l].alive;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin>>n;
    a.resize(n);
    forn(i,0,n) cin>>a[i];

    cin>>Q;
    forn(z,0,Q)
    {
        int t; cin>>t;
        if (t == 1)
        {
            int p; ll val; cin>>p>>val; p--;
            a[p] = val;
        }
        else
        {
            int l,r; cin>>l>>r; l--; r--;
            cout << query(l, r) << '\n';
        }
    }

    return 0;
}

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