oj.uz

Submission #738003

# Submission time Handle Problem Language Result Execution time Memory
738003 2023-05-08T04:57:05 Z resting Fish 2 (JOI22_fish2) C++17
43 / 100
 1863 ms 57968 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mx = 1e5 + 5;
const ll inf = 1e15;


struct segtree2 {
    int l, r, cnt1 = 0, cnt2 = 0, lz = 0;
    segtree2* lc, * rc;
    segtree2* getmem();
    segtree2() : segtree2(-1, -1) {};
    segtree2(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree2(l, m);
        rc = getmem(); *rc = segtree2(m + 1, r);
    }
    void fix() {
        if (l == r) {
            cnt1 = cnt2 = 0;
            if (lz == 1) cnt1 = 1;
            if (lz > 1) cnt2 = 1;
            return;
        }
        if (lz == 0) {
            cnt1 = lc->cnt1 + rc->cnt1;
            cnt2 = lc->cnt2 + rc->cnt2;
        } else if (lz == 1) {
            cnt2 = lc->cnt1 + rc->cnt1 + lc->cnt2 + rc->cnt2;
            cnt1 = (r - l + 1) - cnt2;
        } else {
            cnt1 = 0;
            cnt2 = (r - l + 1);
        }
    }
    void upd(int ql, int qr, int qv) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lz += qv; fix();
            return;
        }
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        fix();
    }
    int q(int ql, int qr, int qlz = 0) {
        if (l > qr || r < ql) return 0;
        lz += qlz; fix();
        int res = 0;
        if (l >= ql && r <= qr) {
            res = cnt2;
        } else {
            res = lc->q(ql, qr, lz) + rc->q(ql, qr, lz);
        }
        lz -= qlz; fix();
        return res;
    }
};
segtree2 mem2[mx * 4];
int memsz2 = 0;
segtree2* segtree2::getmem() { return &mem2[memsz2++]; }
segtree2 ac2;

struct segtree {
    int l, r, v, m;
    segtree* lc, * rc;
    segtree* getmem();
    vector<pair<int, int>> k;
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        m = (l + r) / 2;
        if (l == r)return;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void del(int ql, int qr) {
        if (qr < m) { lc->del(ql, qr); return; }
        if (ql > m) { rc->del(ql, qr); return; }
        k.erase(find(k.begin(), k.end(), pair<int, int>(ql, qr)));
    }
    void add(int ql, int qr) {
        if (qr < m) { lc->add(ql, qr); return; }
        if (ql > m) { rc->add(ql, qr); return; }
        k.push_back({ ql, qr });
    }
    void q(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q(qi);
        else rc->q(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, -1);
                    k.erase(t);
                } else ++t;
            }
        } else {
            for (auto t = k.begin(); t != k.end(); ) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, -1);
                    k.erase(t);
                } else ++t;
            }
        }
    }
    void q2(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q2(qi);
        else rc->q2(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();t++) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, -1);
                }
            }
        } else {
            for (auto t = k.begin(); t != k.end(); t++) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, -1);
                }
            }
        }
    }
    void q3(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q3(qi);
        else rc->q3(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();t++) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, 1);
                }
            }
        } else {
            for (auto t = k.begin(); t != k.end();t++) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, 1);
                }
            }
        }
    }
};
segtree mem[mx * 4];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }


struct segtree3 {
    int l, r; ll mx = 0, sm = 0;
    segtree3* lc, * rc;
    segtree3* getmem();
    segtree3() : segtree3(-1, -1) {};
    segtree3(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree3(l, m);
        rc = getmem(); *rc = segtree3(m + 1, r);
    }
    void fix() {
        if (l == r) return;
        mx = max(lc->mx, rc->mx);
        sm = lc->sm + rc->sm;
    }
    void upd(int qi, ll qv) {
        if (l > qi || r < qi) return;
        if (l == r) {
            mx = qv; sm = qv;return;
        }
        lc->upd(qi, qv); rc->upd(qi, qv);
        fix();
    }
    int walkl(int ql, ll qv) {
        if (r < ql) return -1;
        if (mx <= qv) return -1;
        if (l == r) return l;
        int v = lc->walkl(ql, qv);
        return v == -1 ? rc->walkl(ql, qv) : v;
    }
    int walkr(int qr, ll qv) {
        if (l > qr) return -1;
        if (mx <= qv) return -1;
        if (l == r) return l;
        int v = rc->walkr(qr, qv);
        return v == -1 ? lc->walkr(qr, qv) : v;
    }
    ll qsum(int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return sm;
        return lc->qsum(ql, qr) + rc->qsum(ql, qr);
    }
};
segtree3 mem3[mx * 4];
int memsz3 = 0;
segtree3* segtree3::getmem() { return &mem3[memsz++]; }


segtree ac;  segtree3 ac3; vector<ll> ac4;
int n;

void clear(int i) {
    ac.q(i);
}void clear2(int i) {
    ac.q2(i);
}void clear3(int i) {
    ac.q3(i);
}

void redo(int i, bool extendleft, bool extendright) {
    //cout << "REDO " << i << endl;
    //walking time
    int l = i, r = i;
    while (1) {
        ll t = ac3.qsum(l, r);
        int wr = ac3.walkl(r + 1, t);
        int wl = ac3.walkr(l - 1, t);
        if (wl < i - 1 && !extendleft) break;
        if (wr > i + 1 && !extendright) break;
        if (wl == -1 || wr == -1) break;
        t = ac3.qsum(wl + 1, wr - 1);
        if (ac4[wl] > t && ac4[wr] > t) {
            ac.add(wl + 1, wr - 1);
            ac2.upd(wl + 1, wr - 1, 1);
        }
        l = wl + 1, r = wr - 1;
        if (ac4[wl] > ac4[wr]) {
            if (!extendright) break;
            r++;
        } else {
            if (!extendleft) break;
            l--;
        }
    }
}

void redo2(int i, bool extendleft, bool extendright) {
    //cout << "REDO " << i << endl;
    //walking time
    int l = i, r = i;
    while (1) {
        ll t = ac3.qsum(l, r);
        int wr = ac3.walkl(r + 1, t);
        int wl = ac3.walkr(l - 1, t);
        if (wl < i - 1 && !extendleft) break;
        if (wr > i + 1 && !extendright) break;
        if (wl == -1 || wr == -1) break;
        t = ac3.qsum(wl + 1, wr - 1);
        if (ac4[wl] > t && ac4[wr] > t) {
            ac2.upd(wl + 1, wr - 1, 1);
        }
        l = wl + 1, r = wr - 1;
        if (ac4[wl] > ac4[wr]) {
            if (!extendright) break;
            r++;
        } else {
            if (!extendleft) break;
            l--;
        }
    }
}
void redo3(int i, bool extendleft, bool extendright) {
    //cout << "REDO " << i << endl;
    //walking time
    int l = i, r = i;
    while (1) {
        ll t = ac3.qsum(l, r);
        int wr = ac3.walkl(r + 1, t);
        int wl = ac3.walkr(l - 1, t);
        if (wl < i - 1 && !extendleft) break;
        if (wr > i + 1 && !extendright) break;
        if (wl == -1 || wr == -1) break;
        t = ac3.qsum(wl + 1, wr - 1);
        if (ac4[wl] > t && ac4[wr] > t) {
            ac2.upd(wl + 1, wr - 1, -1);
        }
        l = wl + 1, r = wr - 1;
        if (ac4[wl] > ac4[wr]) {
            if (!extendright) break;
            r++;
        } else {
            if (!extendleft) break;
            l--;
        }
    }
}

void upd(int i, ll v, bool left, bool right) {
    ac4[i] = v; ac3.upd(i, v);
    clear(i);
    if (i < n + 1 && right)clear(i + 1);
    if (i && left)clear(i - 1);

    redo(i, 1, 1);
    if (i < n + 1 && right)redo(i + 1, 0, 1);
    if (i && left)redo(i - 1, 1, 0);
}

void upd2(int i, ll v, bool left, bool right) {
    ac4[i] = v; ac3.upd(i, v);
    clear2(i);
    if (i < n + 1 && right)clear2(i + 1);
    if (i && left)clear2(i - 1);

    redo2(i, 1, 1);
    if (i < n + 1 && right)redo2(i + 1, 0, 1);
    if (i && left)redo2(i - 1, 1, 0);
}

void upd3(int i, ll v, bool left, bool right) {
    clear3(i);
    if (i < n + 1 && right)clear3(i + 1);
    if (i && left)clear3(i - 1);

    redo3(i, 1, 1);
    if (i < n + 1 && right)redo3(i + 1, 0, 1);
    if (i && left)redo3(i - 1, 1, 0);
    ac4[i] = v; ac3.upd(i, v);
}


void solve() {
    cin >> n;
    vector<int> a(n + 1, 0); for (int i = 1; i <= n; i++) cin >> a[i];
    ac = segtree(0, n + 1); ac2 = segtree2(0, n + 1); ac3 = segtree3(0, n + 1); ac4 = vector<ll>(n + 2, 0);
    for (int i = 0; i <= n + 1; i++) { ac4[i] = a[i]; ac3.upd(i, a[i]); }
    for (int i = 0; i <= n + 1; i++) { redo(i, 1, 0); }
    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y; a[x] = y;
            upd(x, y, 1, 1);
        } else {
            int l, r; cin >> l >> r;
            upd(l - 1, inf, 0, 1); upd2(r + 1, inf, 1, 0);
            cout << (r - l + 1 - ac2.q(l, r)) << endl;
            upd3(r + 1, a[r + 1], 1, 0);upd(l - 1, a[l - 1], 0, 1);
        }
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53472 KB Output is correct
2 Correct 109 ms 55836 KB Output is correct
3 Correct 107 ms 55872 KB Output is correct
4 Correct 105 ms 55884 KB Output is correct
5 Correct 122 ms 55892 KB Output is correct
6 Correct 101 ms 55872 KB Output is correct
7 Correct 91 ms 55356 KB Output is correct
8 Correct 99 ms 55912 KB Output is correct
9 Correct 93 ms 55380 KB Output is correct
10 Correct 110 ms 55256 KB Output is correct
11 Correct 105 ms 55420 KB Output is correct
12 Correct 99 ms 55724 KB Output is correct
13 Correct 101 ms 55736 KB Output is correct
14 Correct 113 ms 56404 KB Output is correct
15 Correct 115 ms 56180 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53472 KB Output is correct
2 Correct 109 ms 55836 KB Output is correct
3 Correct 107 ms 55872 KB Output is correct
4 Correct 105 ms 55884 KB Output is correct
5 Correct 122 ms 55892 KB Output is correct
6 Correct 101 ms 55872 KB Output is correct
7 Correct 91 ms 55356 KB Output is correct
8 Correct 99 ms 55912 KB Output is correct
9 Correct 93 ms 55380 KB Output is correct
10 Correct 110 ms 55256 KB Output is correct
11 Correct 105 ms 55420 KB Output is correct
12 Correct 99 ms 55724 KB Output is correct
13 Correct 101 ms 55736 KB Output is correct
14 Correct 113 ms 56404 KB Output is correct
15 Correct 115 ms 56180 KB Output is correct
16 Incorrect 21 ms 53460 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53472 KB Output is correct
2 Correct 109 ms 55836 KB Output is correct
3 Correct 107 ms 55872 KB Output is correct
4 Correct 105 ms 55884 KB Output is correct
5 Correct 122 ms 55892 KB Output is correct
6 Correct 101 ms 55872 KB Output is correct
7 Correct 91 ms 55356 KB Output is correct
8 Correct 99 ms 55912 KB Output is correct
9 Correct 93 ms 55380 KB Output is correct
10 Correct 110 ms 55256 KB Output is correct
11 Correct 105 ms 55420 KB Output is correct
12 Correct 99 ms 55724 KB Output is correct
13 Correct 101 ms 55736 KB Output is correct
14 Correct 113 ms 56404 KB Output is correct
15 Correct 115 ms 56180 KB Output is correct
16 Correct 22 ms 53460 KB Output is correct
17 Correct 1108 ms 56052 KB Output is correct
18 Correct 1086 ms 57968 KB Output is correct
19 Correct 1863 ms 56080 KB Output is correct
20 Correct 1200 ms 57948 KB Output is correct
21 Correct 1295 ms 56272 KB Output is correct
22 Correct 1067 ms 57748 KB Output is correct
23 Correct 1352 ms 56176 KB Output is correct
24 Correct 1121 ms 57936 KB Output is correct
25 Correct 1476 ms 56036 KB Output is correct
26 Correct 752 ms 56816 KB Output is correct
27 Correct 694 ms 56852 KB Output is correct
28 Correct 1025 ms 57136 KB Output is correct
29 Correct 784 ms 56724 KB Output is correct
30 Correct 707 ms 56872 KB Output is correct
31 Correct 1037 ms 57064 KB Output is correct
32 Correct 1033 ms 57292 KB Output is correct
33 Correct 839 ms 55792 KB Output is correct
34 Correct 1038 ms 57532 KB Output is correct
35 Correct 1060 ms 55552 KB Output is correct
36 Correct 1053 ms 57248 KB Output is correct
37 Correct 1073 ms 56716 KB Output is correct
38 Correct 1158 ms 56644 KB Output is correct
39 Correct 876 ms 57268 KB Output is correct
40 Correct 930 ms 56960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53452 KB Output isn't correct
2 Halted 0 ms 0 KB -