oj.uz

Submission #1113310

# Submission time Handle Problem Language Result Execution time Memory
1113310 2024-11-16T10:52:37 Z dwuy Fish 2 (JOI22_fish2) C++14
25 / 100
 4000 ms 53472 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 Tnode{
    int mx, sum;
};

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

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

    Tnode combine(Tnode a, Tnode b){
        return {max(a.mx, b.mx), a.sum + b.sum};
    }

    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, val};
        for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
    }

    int gsum(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].sum;
        int mid = (l + r)>>1;
        return gsum(l, mid, id<<1, u, v)  + gsum(mid + 1, r, id<<1|1, u, v);
    }

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

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

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

    int rmx(int l, int r, int id, const int &pos, const int &val){
        if(r < pos || tree[id].mx <= val) return r + 1;
        if(l == r) return l;
        int mid = (l + r)>>1;
        int p = rmx(l, mid, id<<1, pos, val);
        return p != mid + 1? p : rmx(mid + 1, r, id<<1|1, pos, val);
    }
    
    int rmx(int pos, int val){
        return rmx(1, n, 1, 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 = taiki.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(j, bsum);
                p = max(p, a.l - 1);
                if(p != j){
                    bsum += taiki.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 += taiki.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 += taiki.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 += taiki.gsum(b.pr[i].fi + 1, b.pr[i + 1].fi);
                i++;
            }
        }

        bsum = taiki.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(j, bsum);
                p = min(p, b.r + 1);
                if(p != j){
                    bsum += taiki.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 += taiki.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 += taiki.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 += taiki.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--;
            }
        }

        // sort(res.pr.begin(), res.pr.end());
        // sort(res.pl.begin(), res.pl.end(), greater<pii>());
        // vector<pii> tmp;
        // for(pii p: res.pr){
        //     if(tmp.size() && tmp.back().fi == p.fi) tmp.back().se += p.se;
        //     else tmp.push_back(p);
        // }
        // res.pr = tmp;
        // tmp.clear();
        // for(pii p: res.pl){
        //     if(tmp.size() && tmp.back().fi == p.fi) tmp.back().se += p.se;
        //     else tmp.push_back(p);
        // }
        // res.pl = tmp;
        return res;
    }

    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].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];

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

    for(int i=1; i<=n; i++) taiki.update(i, a[i]);
    for(int i=1; i<=n; i++) chii.update(i, a[i]);
    // chii.show();
    
    int q; cin >> q;
    while(q--){
        int oper, u, v;
        cin >> oper >> u >> v;
        if(oper == 1){
            a[u] = v;
            taiki.update(u, a[u]);
            chii.update(u, a[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 7 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 6 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 5 ms 680 KB Output is correct
13 Correct 5 ms 592 KB Output is correct
14 Correct 7 ms 592 KB Output is correct
15 Correct 4 ms 592 KB Output is correct
16 Correct 6 ms 592 KB Output is correct
17 Correct 5 ms 592 KB Output is correct
18 Correct 4 ms 592 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 4 ms 764 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 209 ms 51624 KB Output is correct
3 Correct 199 ms 50996 KB Output is correct
4 Correct 179 ms 52212 KB Output is correct
5 Correct 198 ms 51016 KB Output is correct
6 Correct 174 ms 47680 KB Output is correct
7 Correct 190 ms 47180 KB Output is correct
8 Correct 167 ms 47008 KB Output is correct
9 Correct 212 ms 47176 KB Output is correct
10 Correct 205 ms 52852 KB Output is correct
11 Correct 195 ms 49992 KB Output is correct
12 Correct 169 ms 47196 KB Output is correct
13 Correct 167 ms 47176 KB Output is correct
14 Correct 180 ms 48200 KB Output is correct
15 Correct 175 ms 48540 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 7 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 6 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 5 ms 680 KB Output is correct
13 Correct 5 ms 592 KB Output is correct
14 Correct 7 ms 592 KB Output is correct
15 Correct 4 ms 592 KB Output is correct
16 Correct 6 ms 592 KB Output is correct
17 Correct 5 ms 592 KB Output is correct
18 Correct 4 ms 592 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 4 ms 764 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Correct 209 ms 51624 KB Output is correct
23 Correct 199 ms 50996 KB Output is correct
24 Correct 179 ms 52212 KB Output is correct
25 Correct 198 ms 51016 KB Output is correct
26 Correct 174 ms 47680 KB Output is correct
27 Correct 190 ms 47180 KB Output is correct
28 Correct 167 ms 47008 KB Output is correct
29 Correct 212 ms 47176 KB Output is correct
30 Correct 205 ms 52852 KB Output is correct
31 Correct 195 ms 49992 KB Output is correct
32 Correct 169 ms 47196 KB Output is correct
33 Correct 167 ms 47176 KB Output is correct
34 Correct 180 ms 48200 KB Output is correct
35 Correct 175 ms 48540 KB Output is correct
36 Correct 226 ms 52288 KB Output is correct
37 Correct 251 ms 51300 KB Output is correct
38 Correct 235 ms 51272 KB Output is correct
39 Correct 226 ms 52296 KB Output is correct
40 Correct 237 ms 50892 KB Output is correct
41 Correct 189 ms 46920 KB Output is correct
42 Correct 184 ms 47752 KB Output is correct
43 Correct 193 ms 47432 KB Output is correct
44 Correct 194 ms 47520 KB Output is correct
45 Correct 255 ms 52836 KB Output is correct
46 Correct 265 ms 53040 KB Output is correct
47 Correct 282 ms 49480 KB Output is correct
48 Correct 177 ms 47436 KB Output is correct
49 Correct 181 ms 47440 KB Output is correct
50 Correct 187 ms 48560 KB Output is correct
51 Correct 183 ms 48384 KB Output is correct
52 Correct 180 ms 48168 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 209 ms 51624 KB Output is correct
3 Correct 199 ms 50996 KB Output is correct
4 Correct 179 ms 52212 KB Output is correct
5 Correct 198 ms 51016 KB Output is correct
6 Correct 174 ms 47680 KB Output is correct
7 Correct 190 ms 47180 KB Output is correct
8 Correct 167 ms 47008 KB Output is correct
9 Correct 212 ms 47176 KB Output is correct
10 Correct 205 ms 52852 KB Output is correct
11 Correct 195 ms 49992 KB Output is correct
12 Correct 169 ms 47196 KB Output is correct
13 Correct 167 ms 47176 KB Output is correct
14 Correct 180 ms 48200 KB Output is correct
15 Correct 175 ms 48540 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Execution timed out 4083 ms 53060 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 209 ms 51624 KB Output is correct
3 Correct 199 ms 50996 KB Output is correct
4 Correct 179 ms 52212 KB Output is correct
5 Correct 198 ms 51016 KB Output is correct
6 Correct 174 ms 47680 KB Output is correct
7 Correct 190 ms 47180 KB Output is correct
8 Correct 167 ms 47008 KB Output is correct
9 Correct 212 ms 47176 KB Output is correct
10 Correct 205 ms 52852 KB Output is correct
11 Correct 195 ms 49992 KB Output is correct
12 Correct 169 ms 47196 KB Output is correct
13 Correct 167 ms 47176 KB Output is correct
14 Correct 180 ms 48200 KB Output is correct
15 Correct 175 ms 48540 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 3099 ms 53472 KB Output is correct
18 Correct 2357 ms 52524 KB Output is correct
19 Correct 2689 ms 51184 KB Output is correct
20 Correct 1770 ms 52552 KB Output is correct
21 Correct 3381 ms 53416 KB Output is correct
22 Correct 2247 ms 51248 KB Output is correct
23 Execution timed out 4054 ms 52064 KB Time limit exceeded
24 Halted 0 ms 0 KB -

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 7 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 6 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 5 ms 680 KB Output is correct
13 Correct 5 ms 592 KB Output is correct
14 Correct 7 ms 592 KB Output is correct
15 Correct 4 ms 592 KB Output is correct
16 Correct 6 ms 592 KB Output is correct
17 Correct 5 ms 592 KB Output is correct
18 Correct 4 ms 592 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 4 ms 764 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Correct 209 ms 51624 KB Output is correct
23 Correct 199 ms 50996 KB Output is correct
24 Correct 179 ms 52212 KB Output is correct
25 Correct 198 ms 51016 KB Output is correct
26 Correct 174 ms 47680 KB Output is correct
27 Correct 190 ms 47180 KB Output is correct
28 Correct 167 ms 47008 KB Output is correct
29 Correct 212 ms 47176 KB Output is correct
30 Correct 205 ms 52852 KB Output is correct
31 Correct 195 ms 49992 KB Output is correct
32 Correct 169 ms 47196 KB Output is correct
33 Correct 167 ms 47176 KB Output is correct
34 Correct 180 ms 48200 KB Output is correct
35 Correct 175 ms 48540 KB Output is correct
36 Correct 226 ms 52288 KB Output is correct
37 Correct 251 ms 51300 KB Output is correct
38 Correct 235 ms 51272 KB Output is correct
39 Correct 226 ms 52296 KB Output is correct
40 Correct 237 ms 50892 KB Output is correct
41 Correct 189 ms 46920 KB Output is correct
42 Correct 184 ms 47752 KB Output is correct
43 Correct 193 ms 47432 KB Output is correct
44 Correct 194 ms 47520 KB Output is correct
45 Correct 255 ms 52836 KB Output is correct
46 Correct 265 ms 53040 KB Output is correct
47 Correct 282 ms 49480 KB Output is correct
48 Correct 177 ms 47436 KB Output is correct
49 Correct 181 ms 47440 KB Output is correct
50 Correct 187 ms 48560 KB Output is correct
51 Correct 183 ms 48384 KB Output is correct
52 Correct 180 ms 48168 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Execution timed out 4083 ms 53060 KB Time limit exceeded
55 Halted 0 ms 0 KB -