oj.uz

Submission #1081612

# Submission time Handle Problem Language Result Execution time Memory
1081612 2024-08-30T08:11:13 Z Evirir Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 6220 KB 
#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--;
    }
};

vector<ii> vp;

int query(int l, int r)
{
    DSU dsu(n);
    for (const auto& [val, p] : vp)
    {
        if (p < l || p > r) continue;
        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];
    forn(i,0,n) vp.pb({a[i], i});
    sort(all(vp));

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 16 ms 5792 KB Output is correct
3 Correct 15 ms 5464 KB Output is correct
4 Correct 17 ms 5844 KB Output is correct
5 Correct 17 ms 5576 KB Output is correct
6 Correct 18 ms 6100 KB Output is correct
7 Correct 15 ms 5472 KB Output is correct
8 Correct 24 ms 6220 KB Output is correct
9 Correct 15 ms 5516 KB Output is correct
10 Correct 20 ms 5836 KB Output is correct
11 Correct 16 ms 5584 KB Output is correct
12 Correct 17 ms 5332 KB Output is correct
13 Correct 16 ms 5332 KB Output is correct
14 Correct 17 ms 5836 KB Output is correct
15 Correct 18 ms 5844 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 16 ms 5792 KB Output is correct
3 Correct 15 ms 5464 KB Output is correct
4 Correct 17 ms 5844 KB Output is correct
5 Correct 17 ms 5576 KB Output is correct
6 Correct 18 ms 6100 KB Output is correct
7 Correct 15 ms 5472 KB Output is correct
8 Correct 24 ms 6220 KB Output is correct
9 Correct 15 ms 5516 KB Output is correct
10 Correct 20 ms 5836 KB Output is correct
11 Correct 16 ms 5584 KB Output is correct
12 Correct 17 ms 5332 KB Output is correct
13 Correct 16 ms 5332 KB Output is correct
14 Correct 17 ms 5836 KB Output is correct
15 Correct 18 ms 5844 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Execution timed out 4086 ms 5756 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 16 ms 5792 KB Output is correct
3 Correct 15 ms 5464 KB Output is correct
4 Correct 17 ms 5844 KB Output is correct
5 Correct 17 ms 5576 KB Output is correct
6 Correct 18 ms 6100 KB Output is correct
7 Correct 15 ms 5472 KB Output is correct
8 Correct 24 ms 6220 KB Output is correct
9 Correct 15 ms 5516 KB Output is correct
10 Correct 20 ms 5836 KB Output is correct
11 Correct 16 ms 5584 KB Output is correct
12 Correct 17 ms 5332 KB Output is correct
13 Correct 16 ms 5332 KB Output is correct
14 Correct 17 ms 5836 KB Output is correct
15 Correct 18 ms 5844 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -