oj.uz

Submission #1113312

# Submission time Handle Problem Language Result Execution time Memory
1113312 2024-11-16T11:04:27 Z dwuy Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 52580 KB 
/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n;
int a[MX];

struct Dwuy{
    int n;
    vector<int> tree;

    Dwuy(int n = 0) : n(n), tree(n + 5, 0) {}

    void update(int idx, int val){
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }

    int gsum(int idx){
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }

    int gsum(int l, int r){
        return gsum(r) - gsum(l - 1);
    }
} dwuy;

struct Taiki{
    int n;
    vector<int> tree;

    Taiki(int n = 0) : n(n), tree(n<<2|3, 0) {}

    void update(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        tree[id] = val;
        for(id>>=1; id; id>>=1) tree[id] = max(tree[id<<1], tree[id<<1|1]);
    }

    int lmx(int l, int r, int id, const int &lim, const int &pos, const int &val){
        if(l > pos || tree[id] <= val) return l - 1;
        if(r < lim) return lim - 1;
        if(l == r) return l;
        int mid = (l + r)>>1;
        int p = lmx(mid + 1, r, id<<1|1, lim, pos, val);
        return p != mid? p : lmx(l, mid, id<<1, lim, pos, val);
    }

    int lmx(int lim, int pos, int val){
        return lmx(1, n, 1, lim, pos, val);
    }

    int rmx(int l, int r, int id, const int &lim, const int &pos, const int &val){
        if(r < pos || tree[id] <= val) return r + 1;
        if(l > lim) return lim + 1;
        if(l == r) return l;
        int mid = (l + r)>>1;
        int p = rmx(l, mid, id<<1, lim, pos, val);
        return p != mid + 1? p : rmx(mid + 1, r, id<<1|1, lim, pos, val);
    }
    
    int rmx(int lim, int pos, int val){
        return rmx(1, n, 1, lim, pos, val);
    }

} taiki;

struct Cnode{
    vector<pii> pl, pr;
    int l, r;
    /// pl: {pl[i], ...} -> pr[i] = R;
    /// pr: {pr[i], ...} -> pl[i] = L;
    Cnode() : pl({}), pr({}), l(0), r(0) {}
};

struct Chii{
    int n;
    vector<Cnode> tree;

    Chii(int n = 0) : n(n), tree(n<<2|3, Cnode()) {}

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

    void build(){
        build(1, n, 1);
    }

    Cnode combine(Cnode a, Cnode b){
        Cnode res;
        res.l = a.l;
        res.r = b.r;
        if(a.pl.size() == 0 || b.pl.size() == 0) return res;

        res.pr = a.pr;
        res.pr.pop_back();
        res.pl = b.pl;
        res.pl.pop_back();

        pii extrLeft = {-1, -1};
        pii extrRight = {-1, -1};

        int bsum = dwuy.gsum(b.l, b.pr[0].fi);
        for(int i=0, j=b.l - 1; i<len(b.pr);){
            while(j >= a.l){
                int p = taiki.lmx(a.l, j, bsum);
                p = max(p, a.l - 1);
                if(p != j){
                    bsum += dwuy.gsum(p + 1, j);
                    j = p;
                    while(i + 1 < len(b.pr) && bsum >= ::a[b.pr[i].fi + 1]){
                        b.pr[i + 1].se += b.pr[i].se;
                        bsum += dwuy.gsum(b.pr[i].fi + 1, b.pr[i + 1].fi);
                        i++;
                    }
                }
                else break;
            }
            if(j < a.l) res.pr.push_back(b.pr[i]);
            i++;
            if(i == len(b.pr)) extrLeft = {j + 1, b.pr.back().se};                
            else bsum += dwuy.gsum(b.pr[i - 1].fi + 1, b.pr[i].fi);
            while(i + 1 < len(b.pr) && bsum >= ::a[b.pr[i].fi + 1]){
                b.pr[i + 1].se += b.pr[i].se;
                bsum += dwuy.gsum(b.pr[i].fi + 1, b.pr[i + 1].fi);
                i++;
            }
        }

        bsum = dwuy.gsum(a.pl[0].fi, a.r);
        for(int i=0, j=a.r + 1; i<len(a.pl); ){
            while(j <= b.r){
                int p = taiki.rmx(b.r, j, bsum);
                p = min(p, b.r + 1);
                if(p != j){
                    bsum += dwuy.gsum(j, p - 1);
                    j = p;
                    while(i + 1 <len(a.pl) && bsum >= ::a[a.pl[i].fi - 1]){
                        a.pl[i + 1].se += a.pl[i].se;
                        bsum += dwuy.gsum(a.pl[i + 1].fi, a.pl[i].fi - 1);
                        i++;
                    }
                }
                else break;
            }
            if(j > b.r) res.pl.push_back(a.pl[i]);
            i++;
            if(i == len(a.pl)) extrRight = {j - 1, a.pl.back().se};
            else bsum += dwuy.gsum(a.pl[i].fi, a.pl[i - 1].fi - 1);
            while(i + 1 <len(a.pl) && bsum >= ::a[a.pl[i].fi - 1]){
                a.pl[i + 1].se += a.pl[i].se;
                bsum += dwuy.gsum(a.pl[i + 1].fi, a.pl[i].fi - 1);
                i++;
            }
        }
        bool flag = 1;
        for(pii &p: res.pr) if(p.fi == extrRight.fi){
            p.se += extrRight.se;
            flag = 0;
        }
        if(flag){
            res.pr.push_back(extrRight);
            int i = len(res.pr) - 1;
            while(i > 0 && res.pr[i].fi < res.pr[i - 1].fi){
                swap(res.pr[i], res.pr[i - 1]);
                i--;
            }
        }
        flag = 1;
        for(pii &p: res.pl) if(p.fi == extrLeft.fi){
            p.se += extrLeft.se;
            flag = 0;
        }
        if(flag){
            res.pl.push_back(extrLeft);
            int i = len(res.pl) - 1;
            while(i > 0 && res.pl[i].fi > res.pl[i - 1].fi){
                swap(res.pl[i], res.pl[i - 1]);
                i--;
            }
        }
        return res;
    }

    void update(int pos){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        tree[id].pl = {{pos, 1}};
        tree[id].pr = {{pos, 1}};
        for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
    }

    Cnode get(int l, int r, int id, const int &u, const int &v){
        if(l >= u && r <= v) return tree[id];
        int mid = (l + r)>>1;
        if(mid >= v) return get(l, mid, id<<1, u, v);
        if(mid < u) return get(mid + 1, r, id<<1|1, u, v);
        return combine(get(l, mid, id<<1, u, v), get(mid + 1, r, id<<1|1, u, v));
    }

    int get(int l, int r){
        Cnode res = get(1, n, 1, l, r);
        return res.pl.back().se;
    }

    void show(int l, int r, int id){
        cout << " === " << l << ' ' << r << " = " << id << endl;
        cout << "pl: "; for(pii p: tree[id].pl) cout << "{" << p.fi << ", " << p.se << "} ";
        cout << endl;
        cout << "pr: "; for(pii p: tree[id].pr) cout << "{" << p.fi << ", " << p.se << "} ";
        cout << endl << endl;
        if(l == r) return;
        int mid = (l + r)>>1;
        show(l, mid, id<<1);
        show(mid + 1, r, id<<1|1);
    }

    void show(){
        show(1, n, 1);
    }
} chii;



int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];

    dwuy = Dwuy(n);
    taiki = Taiki(n);
    chii = Chii(n);
    chii.build();

    for(int i=1; i<=n; i++) dwuy.update(i, a[i]);
    for(int i=1; i<=n; i++) taiki.update(i, a[i]);
    for(int i=1; i<=n; i++) chii.update(i);
    // chii.show();
    
    int q; cin >> q;
    while(q--){
        int oper, u, v;
        cin >> oper >> u >> v;
        if(oper == 1){
            dwuy.update(u, -a[u] + v);
            a[u] = v;
            taiki.update(u, a[u]);
            chii.update(u);
        }
        else{
            cout << chii.get(u, v) << endl;
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 5 ms 732 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 848 KB Output is correct
17 Correct 3 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 3 ms 592 KB Output is correct
20 Correct 3 ms 760 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 155 ms 49892 KB Output is correct
3 Correct 171 ms 48504 KB Output is correct
4 Correct 152 ms 49736 KB Output is correct
5 Correct 155 ms 48712 KB Output is correct
6 Correct 142 ms 45068 KB Output is correct
7 Correct 142 ms 44872 KB Output is correct
8 Correct 138 ms 44548 KB Output is correct
9 Correct 146 ms 44708 KB Output is correct
10 Correct 176 ms 50396 KB Output is correct
11 Correct 189 ms 47620 KB Output is correct
12 Correct 152 ms 44552 KB Output is correct
13 Correct 151 ms 44844 KB Output is correct
14 Correct 145 ms 45896 KB Output is correct
15 Correct 154 ms 46184 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 5 ms 732 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 848 KB Output is correct
17 Correct 3 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 3 ms 592 KB Output is correct
20 Correct 3 ms 760 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 155 ms 49892 KB Output is correct
23 Correct 171 ms 48504 KB Output is correct
24 Correct 152 ms 49736 KB Output is correct
25 Correct 155 ms 48712 KB Output is correct
26 Correct 142 ms 45068 KB Output is correct
27 Correct 142 ms 44872 KB Output is correct
28 Correct 138 ms 44548 KB Output is correct
29 Correct 146 ms 44708 KB Output is correct
30 Correct 176 ms 50396 KB Output is correct
31 Correct 189 ms 47620 KB Output is correct
32 Correct 152 ms 44552 KB Output is correct
33 Correct 151 ms 44844 KB Output is correct
34 Correct 145 ms 45896 KB Output is correct
35 Correct 154 ms 46184 KB Output is correct
36 Correct 179 ms 49992 KB Output is correct
37 Correct 197 ms 48612 KB Output is correct
38 Correct 194 ms 48644 KB Output is correct
39 Correct 189 ms 49992 KB Output is correct
40 Correct 214 ms 48968 KB Output is correct
41 Correct 159 ms 44616 KB Output is correct
42 Correct 158 ms 44872 KB Output is correct
43 Correct 180 ms 44876 KB Output is correct
44 Correct 177 ms 44872 KB Output is correct
45 Correct 236 ms 50516 KB Output is correct
46 Correct 227 ms 50676 KB Output is correct
47 Correct 208 ms 46920 KB Output is correct
48 Correct 158 ms 45000 KB Output is correct
49 Correct 158 ms 44940 KB Output is correct
50 Correct 169 ms 45384 KB Output is correct
51 Correct 171 ms 45640 KB Output is correct
52 Correct 200 ms 45456 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 155 ms 49892 KB Output is correct
3 Correct 171 ms 48504 KB Output is correct
4 Correct 152 ms 49736 KB Output is correct
5 Correct 155 ms 48712 KB Output is correct
6 Correct 142 ms 45068 KB Output is correct
7 Correct 142 ms 44872 KB Output is correct
8 Correct 138 ms 44548 KB Output is correct
9 Correct 146 ms 44708 KB Output is correct
10 Correct 176 ms 50396 KB Output is correct
11 Correct 189 ms 47620 KB Output is correct
12 Correct 152 ms 44552 KB Output is correct
13 Correct 151 ms 44844 KB Output is correct
14 Correct 145 ms 45896 KB Output is correct
15 Correct 154 ms 46184 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2859 ms 50012 KB Output is correct
18 Correct 1981 ms 51832 KB Output is correct
19 Correct 2872 ms 50760 KB Output is correct
20 Correct 2965 ms 50508 KB Output is correct
21 Correct 2789 ms 50696 KB Output is correct
22 Correct 1952 ms 51784 KB Output is correct
23 Correct 2913 ms 50504 KB Output is correct
24 Correct 2903 ms 50552 KB Output is correct
25 Correct 2912 ms 50744 KB Output is correct
26 Correct 2947 ms 50744 KB Output is correct
27 Correct 852 ms 47684 KB Output is correct
28 Correct 858 ms 47432 KB Output is correct
29 Correct 902 ms 47488 KB Output is correct
30 Correct 1614 ms 46708 KB Output is correct
31 Correct 1558 ms 46624 KB Output is correct
32 Correct 3960 ms 49300 KB Output is correct
33 Execution timed out 4067 ms 52580 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 155 ms 49892 KB Output is correct
3 Correct 171 ms 48504 KB Output is correct
4 Correct 152 ms 49736 KB Output is correct
5 Correct 155 ms 48712 KB Output is correct
6 Correct 142 ms 45068 KB Output is correct
7 Correct 142 ms 44872 KB Output is correct
8 Correct 138 ms 44548 KB Output is correct
9 Correct 146 ms 44708 KB Output is correct
10 Correct 176 ms 50396 KB Output is correct
11 Correct 189 ms 47620 KB Output is correct
12 Correct 152 ms 44552 KB Output is correct
13 Correct 151 ms 44844 KB Output is correct
14 Correct 145 ms 45896 KB Output is correct
15 Correct 154 ms 46184 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1928 ms 50576 KB Output is correct
18 Correct 1650 ms 49992 KB Output is correct
19 Correct 1626 ms 49604 KB Output is correct
20 Correct 1161 ms 49800 KB Output is correct
21 Correct 1840 ms 50460 KB Output is correct
22 Correct 1547 ms 50020 KB Output is correct
23 Correct 2446 ms 49236 KB Output is correct
24 Correct 1667 ms 50772 KB Output is correct
25 Correct 2189 ms 49984 KB Output is correct
26 Correct 808 ms 47396 KB Output is correct
27 Correct 1051 ms 47432 KB Output is correct
28 Correct 1112 ms 48220 KB Output is correct
29 Correct 851 ms 47520 KB Output is correct
30 Correct 1088 ms 47444 KB Output is correct
31 Correct 1329 ms 48148 KB Output is correct
32 Correct 1609 ms 49876 KB Output is correct
33 Correct 2078 ms 49172 KB Output is correct
34 Correct 1533 ms 52340 KB Output is correct
35 Correct 1712 ms 51964 KB Output is correct
36 Correct 1395 ms 49340 KB Output is correct
37 Correct 1310 ms 48276 KB Output is correct
38 Correct 856 ms 48084 KB Output is correct
39 Correct 963 ms 47944 KB Output is correct
40 Correct 421 ms 47864 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 5 ms 732 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 848 KB Output is correct
17 Correct 3 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 3 ms 592 KB Output is correct
20 Correct 3 ms 760 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 155 ms 49892 KB Output is correct
23 Correct 171 ms 48504 KB Output is correct
24 Correct 152 ms 49736 KB Output is correct
25 Correct 155 ms 48712 KB Output is correct
26 Correct 142 ms 45068 KB Output is correct
27 Correct 142 ms 44872 KB Output is correct
28 Correct 138 ms 44548 KB Output is correct
29 Correct 146 ms 44708 KB Output is correct
30 Correct 176 ms 50396 KB Output is correct
31 Correct 189 ms 47620 KB Output is correct
32 Correct 152 ms 44552 KB Output is correct
33 Correct 151 ms 44844 KB Output is correct
34 Correct 145 ms 45896 KB Output is correct
35 Correct 154 ms 46184 KB Output is correct
36 Correct 179 ms 49992 KB Output is correct
37 Correct 197 ms 48612 KB Output is correct
38 Correct 194 ms 48644 KB Output is correct
39 Correct 189 ms 49992 KB Output is correct
40 Correct 214 ms 48968 KB Output is correct
41 Correct 159 ms 44616 KB Output is correct
42 Correct 158 ms 44872 KB Output is correct
43 Correct 180 ms 44876 KB Output is correct
44 Correct 177 ms 44872 KB Output is correct
45 Correct 236 ms 50516 KB Output is correct
46 Correct 227 ms 50676 KB Output is correct
47 Correct 208 ms 46920 KB Output is correct
48 Correct 158 ms 45000 KB Output is correct
49 Correct 158 ms 44940 KB Output is correct
50 Correct 169 ms 45384 KB Output is correct
51 Correct 171 ms 45640 KB Output is correct
52 Correct 200 ms 45456 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Correct 2859 ms 50012 KB Output is correct
55 Correct 1981 ms 51832 KB Output is correct
56 Correct 2872 ms 50760 KB Output is correct
57 Correct 2965 ms 50508 KB Output is correct
58 Correct 2789 ms 50696 KB Output is correct
59 Correct 1952 ms 51784 KB Output is correct
60 Correct 2913 ms 50504 KB Output is correct
61 Correct 2903 ms 50552 KB Output is correct
62 Correct 2912 ms 50744 KB Output is correct
63 Correct 2947 ms 50744 KB Output is correct
64 Correct 852 ms 47684 KB Output is correct
65 Correct 858 ms 47432 KB Output is correct
66 Correct 902 ms 47488 KB Output is correct
67 Correct 1614 ms 46708 KB Output is correct
68 Correct 1558 ms 46624 KB Output is correct
69 Correct 3960 ms 49300 KB Output is correct
70 Execution timed out 4067 ms 52580 KB Time limit exceeded
71 Halted 0 ms 0 KB -