oj.uz

Submission #1113347

# Submission time Handle Problem Language Result Execution time Memory
1113347 2024-11-16T12:12:21 Z dwuy Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 231492 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{
    pii pl[35], pr[35];
    int l, r, tl, tr;
    /// pl: {pl[i], ...} -> pr[i] = R;
    /// pr: {pr[i], ...} -> pl[i] = L;
    Cnode() : pl({}), pr({}), l(0), r(0), tl(0), tr(0) {}

    int plsize() { return tl; }
    int prsize() { return tr; }
    pii &plback() { return pl[tl - 1]; }
    pii &prback() { return pr[tr - 1]; }
    void plpush_back(pii p) { pl[tl] = p; tl++; }
    void prpush_back(pii p) { pr[tr] = p; tr++; }
    void plpop_back() { tl--; }
    void prpop_back() { tr--; }
};

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.plsize() == 0 || b.plsize() == 0) return res;
        
        res.tr = a.tr;
        res.tl = b.tl;
        for(int i=0; i<a.prsize(); i++) res.pr[i] = a.pr[i];
        res.prpop_back();
        for(int i=0; i<b.plsize(); i++) res.pl[i] = b.pl[i];
        res.plpop_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<b.prsize();){
            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 < b.prsize() && 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.prpush_back(b.pr[i]);
            i++;
            if(i == b.prsize()) extrLeft = {j + 1, b.prback().se};                
            else bsum += dwuy.gsum(b.pr[i - 1].fi + 1, b.pr[i].fi);
            while(i + 1 < b.prsize() && 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<a.plsize(); ){
            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 <a.plsize() && 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.plpush_back(a.pl[i]);
            i++;
            if(i == a.plsize()) extrRight = {j - 1, a.plback().se};
            else bsum += dwuy.gsum(a.pl[i].fi, a.pl[i - 1].fi - 1);
            while(i + 1 < a.plsize() && 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(int i=0; i<res.prsize(); i++) if(res.pr[i].fi == extrRight.fi){
            res.pr[i].se += extrRight.se;
            flag = 0;
            break;
        }
        if(flag){
            res.prpush_back(extrRight);
            int i = res.prsize() - 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(int i=0; i<res.plsize(); i++) if(res.pl[i].fi == extrLeft.fi){
            res.pl[i].se += extrLeft.se;
            flag = 0;
            break;
        }
        if(flag){
            res.plpush_back(extrLeft);
            int i = res.plsize() - 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].tl = tree[id].tr = 1;
        tree[id].pl[0] = {pos, 1};
        tree[id].pr[0] = {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.plback().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;
}

Compilation message

fish2.cpp: In constructor 'Cnode::Cnode()':
fish2.cpp:110:54: warning: list-initializer for non-class type must not be parenthesized
  110 |     Cnode() : pl({}), pr({}), l(0), r(0), tl(0), tr(0) {}
      |                                                      ^
fish2.cpp:110:54: warning: list-initializer for non-class type must not be parenthesized

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 5 ms 1616 KB Output is correct
6 Correct 4 ms 1616 KB Output is correct
7 Correct 5 ms 1460 KB Output is correct
8 Correct 5 ms 1616 KB Output is correct
9 Correct 5 ms 1652 KB Output is correct
10 Correct 4 ms 1616 KB Output is correct
11 Correct 3 ms 1616 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct
13 Correct 4 ms 1616 KB Output is correct
14 Correct 6 ms 1616 KB Output is correct
15 Correct 4 ms 1616 KB Output is correct
16 Correct 5 ms 1616 KB Output is correct
17 Correct 4 ms 1616 KB Output is correct
18 Correct 4 ms 1616 KB Output is correct
19 Correct 4 ms 1616 KB Output is correct
20 Correct 4 ms 1628 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 429 ms 228696 KB Output is correct
3 Correct 461 ms 228856 KB Output is correct
4 Correct 465 ms 229192 KB Output is correct
5 Correct 443 ms 228424 KB Output is correct
6 Correct 449 ms 229448 KB Output is correct
7 Correct 452 ms 228680 KB Output is correct
8 Correct 446 ms 228512 KB Output is correct
9 Correct 428 ms 228860 KB Output is correct
10 Correct 460 ms 229192 KB Output is correct
11 Correct 453 ms 228792 KB Output is correct
12 Correct 482 ms 228680 KB Output is correct
13 Correct 436 ms 228424 KB Output is correct
14 Correct 424 ms 229124 KB Output is correct
15 Correct 414 ms 229104 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 5 ms 1616 KB Output is correct
6 Correct 4 ms 1616 KB Output is correct
7 Correct 5 ms 1460 KB Output is correct
8 Correct 5 ms 1616 KB Output is correct
9 Correct 5 ms 1652 KB Output is correct
10 Correct 4 ms 1616 KB Output is correct
11 Correct 3 ms 1616 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct
13 Correct 4 ms 1616 KB Output is correct
14 Correct 6 ms 1616 KB Output is correct
15 Correct 4 ms 1616 KB Output is correct
16 Correct 5 ms 1616 KB Output is correct
17 Correct 4 ms 1616 KB Output is correct
18 Correct 4 ms 1616 KB Output is correct
19 Correct 4 ms 1616 KB Output is correct
20 Correct 4 ms 1628 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 429 ms 228696 KB Output is correct
23 Correct 461 ms 228856 KB Output is correct
24 Correct 465 ms 229192 KB Output is correct
25 Correct 443 ms 228424 KB Output is correct
26 Correct 449 ms 229448 KB Output is correct
27 Correct 452 ms 228680 KB Output is correct
28 Correct 446 ms 228512 KB Output is correct
29 Correct 428 ms 228860 KB Output is correct
30 Correct 460 ms 229192 KB Output is correct
31 Correct 453 ms 228792 KB Output is correct
32 Correct 482 ms 228680 KB Output is correct
33 Correct 436 ms 228424 KB Output is correct
34 Correct 424 ms 229124 KB Output is correct
35 Correct 414 ms 229104 KB Output is correct
36 Correct 421 ms 228684 KB Output is correct
37 Correct 430 ms 228936 KB Output is correct
38 Correct 422 ms 228876 KB Output is correct
39 Correct 458 ms 229188 KB Output is correct
40 Correct 483 ms 228944 KB Output is correct
41 Correct 444 ms 228672 KB Output is correct
42 Correct 451 ms 229448 KB Output is correct
43 Correct 443 ms 228680 KB Output is correct
44 Correct 439 ms 228856 KB Output is correct
45 Correct 486 ms 229192 KB Output is correct
46 Correct 483 ms 228960 KB Output is correct
47 Correct 482 ms 228680 KB Output is correct
48 Correct 440 ms 228936 KB Output is correct
49 Correct 435 ms 228936 KB Output is correct
50 Correct 462 ms 229192 KB Output is correct
51 Correct 454 ms 229224 KB Output is correct
52 Correct 454 ms 229192 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 429 ms 228696 KB Output is correct
3 Correct 461 ms 228856 KB Output is correct
4 Correct 465 ms 229192 KB Output is correct
5 Correct 443 ms 228424 KB Output is correct
6 Correct 449 ms 229448 KB Output is correct
7 Correct 452 ms 228680 KB Output is correct
8 Correct 446 ms 228512 KB Output is correct
9 Correct 428 ms 228860 KB Output is correct
10 Correct 460 ms 229192 KB Output is correct
11 Correct 453 ms 228792 KB Output is correct
12 Correct 482 ms 228680 KB Output is correct
13 Correct 436 ms 228424 KB Output is correct
14 Correct 424 ms 229124 KB Output is correct
15 Correct 414 ms 229104 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2954 ms 229668 KB Output is correct
18 Correct 2319 ms 230836 KB Output is correct
19 Correct 3245 ms 228976 KB Output is correct
20 Correct 3107 ms 230532 KB Output is correct
21 Correct 2981 ms 230504 KB Output is correct
22 Correct 2318 ms 230904 KB Output is correct
23 Correct 3339 ms 230356 KB Output is correct
24 Correct 3183 ms 230532 KB Output is correct
25 Correct 3608 ms 230664 KB Output is correct
26 Correct 3151 ms 229048 KB Output is correct
27 Correct 1151 ms 229208 KB Output is correct
28 Correct 1080 ms 231468 KB Output is correct
29 Correct 1056 ms 231492 KB Output is correct
30 Correct 1800 ms 228884 KB Output is correct
31 Correct 1881 ms 230320 KB Output is correct
32 Execution timed out 4088 ms 230452 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 429 ms 228696 KB Output is correct
3 Correct 461 ms 228856 KB Output is correct
4 Correct 465 ms 229192 KB Output is correct
5 Correct 443 ms 228424 KB Output is correct
6 Correct 449 ms 229448 KB Output is correct
7 Correct 452 ms 228680 KB Output is correct
8 Correct 446 ms 228512 KB Output is correct
9 Correct 428 ms 228860 KB Output is correct
10 Correct 460 ms 229192 KB Output is correct
11 Correct 453 ms 228792 KB Output is correct
12 Correct 482 ms 228680 KB Output is correct
13 Correct 436 ms 228424 KB Output is correct
14 Correct 424 ms 229124 KB Output is correct
15 Correct 414 ms 229104 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1969 ms 229064 KB Output is correct
18 Correct 1712 ms 230216 KB Output is correct
19 Correct 1906 ms 229472 KB Output is correct
20 Correct 1375 ms 229924 KB Output is correct
21 Correct 2171 ms 230244 KB Output is correct
22 Correct 1712 ms 229940 KB Output is correct
23 Correct 2412 ms 229992 KB Output is correct
24 Correct 1822 ms 228680 KB Output is correct
25 Correct 2369 ms 229976 KB Output is correct
26 Correct 1025 ms 231136 KB Output is correct
27 Correct 1325 ms 231260 KB Output is correct
28 Correct 1350 ms 230312 KB Output is correct
29 Correct 1089 ms 231100 KB Output is correct
30 Correct 1110 ms 231328 KB Output is correct
31 Correct 1419 ms 230388 KB Output is correct
32 Correct 1796 ms 228712 KB Output is correct
33 Correct 2320 ms 229784 KB Output is correct
34 Correct 1752 ms 230972 KB Output is correct
35 Correct 1953 ms 230540 KB Output is correct
36 Correct 1441 ms 230472 KB Output is correct
37 Correct 1487 ms 230084 KB Output is correct
38 Correct 1088 ms 230400 KB Output is correct
39 Correct 1182 ms 230960 KB Output is correct
40 Correct 688 ms 230728 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 5 ms 1616 KB Output is correct
6 Correct 4 ms 1616 KB Output is correct
7 Correct 5 ms 1460 KB Output is correct
8 Correct 5 ms 1616 KB Output is correct
9 Correct 5 ms 1652 KB Output is correct
10 Correct 4 ms 1616 KB Output is correct
11 Correct 3 ms 1616 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct
13 Correct 4 ms 1616 KB Output is correct
14 Correct 6 ms 1616 KB Output is correct
15 Correct 4 ms 1616 KB Output is correct
16 Correct 5 ms 1616 KB Output is correct
17 Correct 4 ms 1616 KB Output is correct
18 Correct 4 ms 1616 KB Output is correct
19 Correct 4 ms 1616 KB Output is correct
20 Correct 4 ms 1628 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 429 ms 228696 KB Output is correct
23 Correct 461 ms 228856 KB Output is correct
24 Correct 465 ms 229192 KB Output is correct
25 Correct 443 ms 228424 KB Output is correct
26 Correct 449 ms 229448 KB Output is correct
27 Correct 452 ms 228680 KB Output is correct
28 Correct 446 ms 228512 KB Output is correct
29 Correct 428 ms 228860 KB Output is correct
30 Correct 460 ms 229192 KB Output is correct
31 Correct 453 ms 228792 KB Output is correct
32 Correct 482 ms 228680 KB Output is correct
33 Correct 436 ms 228424 KB Output is correct
34 Correct 424 ms 229124 KB Output is correct
35 Correct 414 ms 229104 KB Output is correct
36 Correct 421 ms 228684 KB Output is correct
37 Correct 430 ms 228936 KB Output is correct
38 Correct 422 ms 228876 KB Output is correct
39 Correct 458 ms 229188 KB Output is correct
40 Correct 483 ms 228944 KB Output is correct
41 Correct 444 ms 228672 KB Output is correct
42 Correct 451 ms 229448 KB Output is correct
43 Correct 443 ms 228680 KB Output is correct
44 Correct 439 ms 228856 KB Output is correct
45 Correct 486 ms 229192 KB Output is correct
46 Correct 483 ms 228960 KB Output is correct
47 Correct 482 ms 228680 KB Output is correct
48 Correct 440 ms 228936 KB Output is correct
49 Correct 435 ms 228936 KB Output is correct
50 Correct 462 ms 229192 KB Output is correct
51 Correct 454 ms 229224 KB Output is correct
52 Correct 454 ms 229192 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Correct 2954 ms 229668 KB Output is correct
55 Correct 2319 ms 230836 KB Output is correct
56 Correct 3245 ms 228976 KB Output is correct
57 Correct 3107 ms 230532 KB Output is correct
58 Correct 2981 ms 230504 KB Output is correct
59 Correct 2318 ms 230904 KB Output is correct
60 Correct 3339 ms 230356 KB Output is correct
61 Correct 3183 ms 230532 KB Output is correct
62 Correct 3608 ms 230664 KB Output is correct
63 Correct 3151 ms 229048 KB Output is correct
64 Correct 1151 ms 229208 KB Output is correct
65 Correct 1080 ms 231468 KB Output is correct
66 Correct 1056 ms 231492 KB Output is correct
67 Correct 1800 ms 228884 KB Output is correct
68 Correct 1881 ms 230320 KB Output is correct
69 Execution timed out 4088 ms 230452 KB Time limit exceeded
70 Halted 0 ms 0 KB -