oj.uz

Submission #1113306

# Submission time Handle Problem Language Result Execution time Memory
1113306 2024-11-16T10:36:38 Z dwuy Fish 2 (JOI22_fish2) C++14
25 / 100
 4000 ms 54504 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();

        int bsum = taiki.gsum(b.l, b.pr[0].fi);
        for(int i=0, j=b.l - 1; i<len(b.pr);){
            while(1){
                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)) res.pl.push_back({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(1){
                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(a.l == 1 && b.r == n) cout << i << ' ' << a.pl[i].se << ' ' << j << ' ' << bsum << endl;
            if(j > b.r) res.pl.push_back(a.pl[i]);
            i++;
            if(i == len(a.pl)) res.pr.push_back({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++;
            }
        }

        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}};
        // cout << id << " - " << tree[id].l << ' ' << tree[id].r << ' ' << pos << endl;
        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);
        assert(res.pl.size());
        // cout << "gettttt" << endl;
        // cout << "pl: "; for(pii p: res.pl) cout << "{" << p.fi << ", " << p.se << "} ";
        // cout << endl;
        // cout << "pr: "; for(pii p: res.pr) cout << "{" << p.fi << ", " << p.se << "} ";
        // cout << endl << endl;
        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 9 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 7 ms 592 KB Output is correct
8 Correct 6 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 4 ms 592 KB Output is correct
12 Correct 5 ms 592 KB Output is correct
13 Correct 6 ms 592 KB Output is correct
14 Correct 8 ms 592 KB Output is correct
15 Correct 6 ms 592 KB Output is correct
16 Correct 7 ms 592 KB Output is correct
17 Correct 6 ms 736 KB Output is correct
18 Correct 6 ms 592 KB Output is correct
19 Correct 5 ms 592 KB Output is correct
20 Correct 9 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 225 ms 53104 KB Output is correct
3 Correct 233 ms 51664 KB Output is correct
4 Correct 222 ms 53100 KB Output is correct
5 Correct 214 ms 51784 KB Output is correct
6 Correct 188 ms 50000 KB Output is correct
7 Correct 203 ms 49224 KB Output is correct
8 Correct 186 ms 49996 KB Output is correct
9 Correct 195 ms 49236 KB Output is correct
10 Correct 236 ms 53812 KB Output is correct
11 Correct 215 ms 51528 KB Output is correct
12 Correct 202 ms 49168 KB Output is correct
13 Correct 210 ms 49224 KB Output is correct
14 Correct 208 ms 49480 KB Output is correct
15 Correct 208 ms 49876 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 9 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 7 ms 592 KB Output is correct
8 Correct 6 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 4 ms 592 KB Output is correct
12 Correct 5 ms 592 KB Output is correct
13 Correct 6 ms 592 KB Output is correct
14 Correct 8 ms 592 KB Output is correct
15 Correct 6 ms 592 KB Output is correct
16 Correct 7 ms 592 KB Output is correct
17 Correct 6 ms 736 KB Output is correct
18 Correct 6 ms 592 KB Output is correct
19 Correct 5 ms 592 KB Output is correct
20 Correct 9 ms 592 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 225 ms 53104 KB Output is correct
23 Correct 233 ms 51664 KB Output is correct
24 Correct 222 ms 53100 KB Output is correct
25 Correct 214 ms 51784 KB Output is correct
26 Correct 188 ms 50000 KB Output is correct
27 Correct 203 ms 49224 KB Output is correct
28 Correct 186 ms 49996 KB Output is correct
29 Correct 195 ms 49236 KB Output is correct
30 Correct 236 ms 53812 KB Output is correct
31 Correct 215 ms 51528 KB Output is correct
32 Correct 202 ms 49168 KB Output is correct
33 Correct 210 ms 49224 KB Output is correct
34 Correct 208 ms 49480 KB Output is correct
35 Correct 208 ms 49876 KB Output is correct
36 Correct 263 ms 53320 KB Output is correct
37 Correct 258 ms 51784 KB Output is correct
38 Correct 261 ms 51784 KB Output is correct
39 Correct 251 ms 53064 KB Output is correct
40 Correct 276 ms 51528 KB Output is correct
41 Correct 201 ms 49992 KB Output is correct
42 Correct 220 ms 49992 KB Output is correct
43 Correct 236 ms 49224 KB Output is correct
44 Correct 242 ms 49228 KB Output is correct
45 Correct 296 ms 54088 KB Output is correct
46 Correct 301 ms 54072 KB Output is correct
47 Correct 311 ms 51280 KB Output is correct
48 Correct 212 ms 49224 KB Output is correct
49 Correct 203 ms 49236 KB Output is correct
50 Correct 210 ms 49488 KB Output is correct
51 Correct 222 ms 49992 KB Output is correct
52 Correct 206 ms 49552 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 225 ms 53104 KB Output is correct
3 Correct 233 ms 51664 KB Output is correct
4 Correct 222 ms 53100 KB Output is correct
5 Correct 214 ms 51784 KB Output is correct
6 Correct 188 ms 50000 KB Output is correct
7 Correct 203 ms 49224 KB Output is correct
8 Correct 186 ms 49996 KB Output is correct
9 Correct 195 ms 49236 KB Output is correct
10 Correct 236 ms 53812 KB Output is correct
11 Correct 215 ms 51528 KB Output is correct
12 Correct 202 ms 49168 KB Output is correct
13 Correct 210 ms 49224 KB Output is correct
14 Correct 208 ms 49480 KB Output is correct
15 Correct 208 ms 49876 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Execution timed out 4066 ms 53072 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 336 KB Output is correct
2 Correct 225 ms 53104 KB Output is correct
3 Correct 233 ms 51664 KB Output is correct
4 Correct 222 ms 53100 KB Output is correct
5 Correct 214 ms 51784 KB Output is correct
6 Correct 188 ms 50000 KB Output is correct
7 Correct 203 ms 49224 KB Output is correct
8 Correct 186 ms 49996 KB Output is correct
9 Correct 195 ms 49236 KB Output is correct
10 Correct 236 ms 53812 KB Output is correct
11 Correct 215 ms 51528 KB Output is correct
12 Correct 202 ms 49168 KB Output is correct
13 Correct 210 ms 49224 KB Output is correct
14 Correct 208 ms 49480 KB Output is correct
15 Correct 208 ms 49876 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 3756 ms 54504 KB Output is correct
18 Correct 2624 ms 53512 KB Output is correct
19 Correct 3307 ms 52900 KB Output is correct
20 Correct 2017 ms 53400 KB Output is correct
21 Correct 3588 ms 54384 KB Output is correct
22 Correct 2554 ms 53488 KB Output is correct
23 Execution timed out 4069 ms 52664 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 9 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 7 ms 592 KB Output is correct
8 Correct 6 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 4 ms 592 KB Output is correct
12 Correct 5 ms 592 KB Output is correct
13 Correct 6 ms 592 KB Output is correct
14 Correct 8 ms 592 KB Output is correct
15 Correct 6 ms 592 KB Output is correct
16 Correct 7 ms 592 KB Output is correct
17 Correct 6 ms 736 KB Output is correct
18 Correct 6 ms 592 KB Output is correct
19 Correct 5 ms 592 KB Output is correct
20 Correct 9 ms 592 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 225 ms 53104 KB Output is correct
23 Correct 233 ms 51664 KB Output is correct
24 Correct 222 ms 53100 KB Output is correct
25 Correct 214 ms 51784 KB Output is correct
26 Correct 188 ms 50000 KB Output is correct
27 Correct 203 ms 49224 KB Output is correct
28 Correct 186 ms 49996 KB Output is correct
29 Correct 195 ms 49236 KB Output is correct
30 Correct 236 ms 53812 KB Output is correct
31 Correct 215 ms 51528 KB Output is correct
32 Correct 202 ms 49168 KB Output is correct
33 Correct 210 ms 49224 KB Output is correct
34 Correct 208 ms 49480 KB Output is correct
35 Correct 208 ms 49876 KB Output is correct
36 Correct 263 ms 53320 KB Output is correct
37 Correct 258 ms 51784 KB Output is correct
38 Correct 261 ms 51784 KB Output is correct
39 Correct 251 ms 53064 KB Output is correct
40 Correct 276 ms 51528 KB Output is correct
41 Correct 201 ms 49992 KB Output is correct
42 Correct 220 ms 49992 KB Output is correct
43 Correct 236 ms 49224 KB Output is correct
44 Correct 242 ms 49228 KB Output is correct
45 Correct 296 ms 54088 KB Output is correct
46 Correct 301 ms 54072 KB Output is correct
47 Correct 311 ms 51280 KB Output is correct
48 Correct 212 ms 49224 KB Output is correct
49 Correct 203 ms 49236 KB Output is correct
50 Correct 210 ms 49488 KB Output is correct
51 Correct 222 ms 49992 KB Output is correct
52 Correct 206 ms 49552 KB Output is correct
53 Correct 2 ms 336 KB Output is correct
54 Execution timed out 4066 ms 53072 KB Time limit exceeded
55 Halted 0 ms 0 KB -