oj.uz

Submission #1113321

# Submission time Handle Problem Language Result Execution time Memory
1113321 2024-11-16T11:20:05 Z dwuy Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 40596 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"

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<ll> tree;

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

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

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

    ll 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 ll &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, ll val){
        return lmx(1, n, 1, lim, pos, val);
    }

    int rmx(int l, int r, int id, const int &lim, const int &pos, const ll &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, ll 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};

        ll 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 632 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 592 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 5 ms 592 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 592 KB Output is correct
17 Correct 4 ms 592 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 3 ms 592 KB Output is correct
20 Correct 3 ms 592 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 167 ms 40060 KB Output is correct
3 Correct 157 ms 39496 KB Output is correct
4 Correct 150 ms 40008 KB Output is correct
5 Correct 155 ms 39496 KB Output is correct
6 Correct 179 ms 37712 KB Output is correct
7 Correct 153 ms 37704 KB Output is correct
8 Correct 148 ms 37704 KB Output is correct
9 Correct 147 ms 37660 KB Output is correct
10 Correct 170 ms 40220 KB Output is correct
11 Correct 167 ms 38984 KB Output is correct
12 Correct 141 ms 37704 KB Output is correct
13 Correct 144 ms 37704 KB Output is correct
14 Correct 167 ms 37708 KB Output is correct
15 Correct 150 ms 37960 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 632 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 592 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 5 ms 592 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 592 KB Output is correct
17 Correct 4 ms 592 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 3 ms 592 KB Output is correct
20 Correct 3 ms 592 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 167 ms 40060 KB Output is correct
23 Correct 157 ms 39496 KB Output is correct
24 Correct 150 ms 40008 KB Output is correct
25 Correct 155 ms 39496 KB Output is correct
26 Correct 179 ms 37712 KB Output is correct
27 Correct 153 ms 37704 KB Output is correct
28 Correct 148 ms 37704 KB Output is correct
29 Correct 147 ms 37660 KB Output is correct
30 Correct 170 ms 40220 KB Output is correct
31 Correct 167 ms 38984 KB Output is correct
32 Correct 141 ms 37704 KB Output is correct
33 Correct 144 ms 37704 KB Output is correct
34 Correct 167 ms 37708 KB Output is correct
35 Correct 150 ms 37960 KB Output is correct
36 Correct 173 ms 39916 KB Output is correct
37 Correct 188 ms 39452 KB Output is correct
38 Correct 213 ms 39504 KB Output is correct
39 Correct 174 ms 39948 KB Output is correct
40 Correct 196 ms 39504 KB Output is correct
41 Correct 161 ms 37704 KB Output is correct
42 Correct 166 ms 37664 KB Output is correct
43 Correct 179 ms 37960 KB Output is correct
44 Correct 179 ms 37708 KB Output is correct
45 Correct 232 ms 40220 KB Output is correct
46 Correct 209 ms 40224 KB Output is correct
47 Correct 207 ms 39024 KB Output is correct
48 Correct 160 ms 37640 KB Output is correct
49 Correct 157 ms 37704 KB Output is correct
50 Correct 166 ms 37708 KB Output is correct
51 Correct 180 ms 37960 KB Output is correct
52 Correct 158 ms 37712 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 167 ms 40060 KB Output is correct
3 Correct 157 ms 39496 KB Output is correct
4 Correct 150 ms 40008 KB Output is correct
5 Correct 155 ms 39496 KB Output is correct
6 Correct 179 ms 37712 KB Output is correct
7 Correct 153 ms 37704 KB Output is correct
8 Correct 148 ms 37704 KB Output is correct
9 Correct 147 ms 37660 KB Output is correct
10 Correct 170 ms 40220 KB Output is correct
11 Correct 167 ms 38984 KB Output is correct
12 Correct 141 ms 37704 KB Output is correct
13 Correct 144 ms 37704 KB Output is correct
14 Correct 167 ms 37708 KB Output is correct
15 Correct 150 ms 37960 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 3053 ms 39792 KB Output is correct
18 Correct 2033 ms 40524 KB Output is correct
19 Correct 3037 ms 39796 KB Output is correct
20 Correct 3139 ms 39712 KB Output is correct
21 Correct 3173 ms 39940 KB Output is correct
22 Correct 2067 ms 40480 KB Output is correct
23 Correct 3304 ms 40024 KB Output is correct
24 Correct 3089 ms 39752 KB Output is correct
25 Correct 2969 ms 39888 KB Output is correct
26 Correct 3035 ms 39768 KB Output is correct
27 Correct 875 ms 38104 KB Output is correct
28 Correct 942 ms 38176 KB Output is correct
29 Correct 890 ms 38232 KB Output is correct
30 Correct 1652 ms 37908 KB Output is correct
31 Correct 1555 ms 37864 KB Output is correct
32 Execution timed out 4077 ms 39396 KB Time limit exceeded
33 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 167 ms 40060 KB Output is correct
3 Correct 157 ms 39496 KB Output is correct
4 Correct 150 ms 40008 KB Output is correct
5 Correct 155 ms 39496 KB Output is correct
6 Correct 179 ms 37712 KB Output is correct
7 Correct 153 ms 37704 KB Output is correct
8 Correct 148 ms 37704 KB Output is correct
9 Correct 147 ms 37660 KB Output is correct
10 Correct 170 ms 40220 KB Output is correct
11 Correct 167 ms 38984 KB Output is correct
12 Correct 141 ms 37704 KB Output is correct
13 Correct 144 ms 37704 KB Output is correct
14 Correct 167 ms 37708 KB Output is correct
15 Correct 150 ms 37960 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2472 ms 40180 KB Output is correct
18 Correct 1620 ms 39668 KB Output is correct
19 Correct 1596 ms 39752 KB Output is correct
20 Correct 1195 ms 40040 KB Output is correct
21 Correct 1853 ms 40268 KB Output is correct
22 Correct 1585 ms 39704 KB Output is correct
23 Correct 2315 ms 39708 KB Output is correct
24 Correct 1551 ms 39828 KB Output is correct
25 Correct 2077 ms 39752 KB Output is correct
26 Correct 692 ms 37980 KB Output is correct
27 Correct 931 ms 37808 KB Output is correct
28 Correct 1063 ms 38608 KB Output is correct
29 Correct 809 ms 37704 KB Output is correct
30 Correct 959 ms 37968 KB Output is correct
31 Correct 1328 ms 38464 KB Output is correct
32 Correct 1583 ms 39384 KB Output is correct
33 Correct 2096 ms 39216 KB Output is correct
34 Correct 1416 ms 40508 KB Output is correct
35 Correct 1648 ms 40596 KB Output is correct
36 Correct 1301 ms 39240 KB Output is correct
37 Correct 1307 ms 38732 KB Output is correct
38 Correct 900 ms 38728 KB Output is correct
39 Correct 862 ms 38228 KB Output is correct
40 Correct 413 ms 38484 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 632 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 592 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 5 ms 592 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 592 KB Output is correct
17 Correct 4 ms 592 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 3 ms 592 KB Output is correct
20 Correct 3 ms 592 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 167 ms 40060 KB Output is correct
23 Correct 157 ms 39496 KB Output is correct
24 Correct 150 ms 40008 KB Output is correct
25 Correct 155 ms 39496 KB Output is correct
26 Correct 179 ms 37712 KB Output is correct
27 Correct 153 ms 37704 KB Output is correct
28 Correct 148 ms 37704 KB Output is correct
29 Correct 147 ms 37660 KB Output is correct
30 Correct 170 ms 40220 KB Output is correct
31 Correct 167 ms 38984 KB Output is correct
32 Correct 141 ms 37704 KB Output is correct
33 Correct 144 ms 37704 KB Output is correct
34 Correct 167 ms 37708 KB Output is correct
35 Correct 150 ms 37960 KB Output is correct
36 Correct 173 ms 39916 KB Output is correct
37 Correct 188 ms 39452 KB Output is correct
38 Correct 213 ms 39504 KB Output is correct
39 Correct 174 ms 39948 KB Output is correct
40 Correct 196 ms 39504 KB Output is correct
41 Correct 161 ms 37704 KB Output is correct
42 Correct 166 ms 37664 KB Output is correct
43 Correct 179 ms 37960 KB Output is correct
44 Correct 179 ms 37708 KB Output is correct
45 Correct 232 ms 40220 KB Output is correct
46 Correct 209 ms 40224 KB Output is correct
47 Correct 207 ms 39024 KB Output is correct
48 Correct 160 ms 37640 KB Output is correct
49 Correct 157 ms 37704 KB Output is correct
50 Correct 166 ms 37708 KB Output is correct
51 Correct 180 ms 37960 KB Output is correct
52 Correct 158 ms 37712 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Correct 3053 ms 39792 KB Output is correct
55 Correct 2033 ms 40524 KB Output is correct
56 Correct 3037 ms 39796 KB Output is correct
57 Correct 3139 ms 39712 KB Output is correct
58 Correct 3173 ms 39940 KB Output is correct
59 Correct 2067 ms 40480 KB Output is correct
60 Correct 3304 ms 40024 KB Output is correct
61 Correct 3089 ms 39752 KB Output is correct
62 Correct 2969 ms 39888 KB Output is correct
63 Correct 3035 ms 39768 KB Output is correct
64 Correct 875 ms 38104 KB Output is correct
65 Correct 942 ms 38176 KB Output is correct
66 Correct 890 ms 38232 KB Output is correct
67 Correct 1652 ms 37908 KB Output is correct
68 Correct 1555 ms 37864 KB Output is correct
69 Execution timed out 4077 ms 39396 KB Time limit exceeded
70 Halted 0 ms 0 KB -