oj.uz

Submission #847962

# Submission time Handle Problem Language Result Execution time Memory
847962 2023-09-10T23:54:48 Z resting Modern Machine (JOI23_ho_t5) C++17
36 / 100
 3000 ms 830936 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mx = 1.2e5 + 5;

const int magic = 1000;
//const int magic = 3;

namespace rmq {
    struct segtree {
        segtree* lc = 0, * rc = 0;
        int l, r;
        int v = numeric_limits<int>::max();
        segtree* getmem();
        segtree() : segtree(-1, -1) {};
        segtree(int l, int r) : l(l), r(r) {
            if (l == r)return;
            int m = (l + r) / 2;
            lc = getmem(); *lc = segtree(l, m);
            rc = getmem(); *rc = segtree(m + 1, r);
        };
        segtree* upd(int qi, int qv) {
            segtree* tr = getmem(); *tr = *this;
            if (qi < l || qi > r) return tr;
            if (l == r) { tr->v = qv; return tr; }
            tr->lc = lc->upd(qi, qv); tr->rc = rc->upd(qi, qv);
            tr->v = min(tr->lc->v, tr->rc->v);
            return tr;
        }
        int q(int ql, int qr) {
            if (ql > qr)return numeric_limits<int>::max();
            if (ql > r || qr < l) return numeric_limits<int>::max();
            if (ql <= l && qr >= r) return v;
            return min(lc->q(ql, qr), rc->q(ql, qr));
        }
    }mem[mx * 50]; int memsz = 0;// surely enogh?
    segtree* segtree::getmem() { return &mem[memsz++]; }
}

namespace rsq {
    struct segtree {
        segtree* lc = 0, * rc = 0;
        int l, r;
        int v = 0;
        segtree* getmem();
        segtree() : segtree(-1, -1) {};
        segtree(int l, int r) : l(l), r(r) {
            if (l == r)return;
            int m = (l + r) / 2;
            lc = getmem(); *lc = segtree(l, m);
            rc = getmem(); *rc = segtree(m + 1, r);
        };
        segtree* upd(int qi, int qv) {
            segtree* tr = getmem(); *tr = *this;
            if (qi < l || qi > r) return tr;
            if (l == r) { tr->v += qv; return tr; }
            tr->lc = lc->upd(qi, qv); tr->rc = rc->upd(qi, qv);
            tr->v = tr->lc->v + tr->rc->v;
            return tr;
        }
        int q(int ql, int qr) {
            if (ql > qr) return 0;
            if (ql > r || qr < l) return 0;
            if (ql <= l && qr >= r) return v;
            return lc->q(ql, qr) + rc->q(ql, qr);
        }
    }mem[mx * 100]; int memsz = 0;// surely enogh?
    segtree* segtree::getmem() { return &mem[memsz++]; }
}

struct bit {
    vector<int> b, a;
    bit(int n) : b(n + 1, 0), a(n + 1, 0) {};
    int q(int i) { int v = 0; for (i++; i > 0; i -= i & -i) v += b[i]; return v; }
    void u(int i, int v) { if (i < a.size()) a[i] += v; for (i++; i < b.size(); i += i & -i) b[i] += v; }
    void u(int l, int r, int v) { if (l > r) return; u(l, v);  u(r + 1, -v); }
};



int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    string c; cin >> c;
    vector<int> a(m); for (auto& x : a) { cin >> x;  x--; }
    vector<vector<int>> a2(n + 1);
    for (int i = 0; i < m; i++) a2[a[i]].push_back(i);
    vector<int> ls, rs;
    ls.push_back(-1); rs.push_back(n);
    for (int i = 0; i < n; i++) if (c[i] == 'B') ls.push_back(i);
    for (int i = n - 1; i >= 0; i--) if (c[i] == 'R') rs.push_back(i);

    vector<int> pre(n, 0);
    for (int i = 0; i < n; i++) {
        if (i) pre[i] = pre[i - 1];
        pre[i] += c[i] == 'R';
    }

    auto sm = [&](int l, int r) {
        if (l > r) return 0LL;
        if (l > n) l = n;
        if (r > n - 1) r = n - 1;
        if (r < 0) return 0LL;
        if (l <= 0) return pre[r];
        return pre[r] - pre[l - 1];
    }; //very necessary yk

    rmq::segtree* tmp = new rmq::segtree(0, n - 1);
    vector<rmq::segtree*> ac(m, 0);
    for (int i = m - 1; i >= 0; i--) {
        ac[i] = tmp = tmp->upd(a[i], i);
        //cout << ac[i]->v << endl;
    }

    rsq::segtree* tmp2 = new rsq::segtree(0, m - 1);
    vector<rsq::segtree*> ac2(n + 1, 0);
    for (int i = 0; i <= n; i++) {
        for (auto& x : a2[i]) tmp2 = tmp2->upd(x, i + 1);
        ac2[i] = tmp2;
    }

    rsq::segtree* tmp3 = new rsq::segtree(0, m - 1);
    vector<rsq::segtree*> ac3(n + 1, 0);
    for (int i = n; i >= 0; i--) {
        for (auto& x : a2[i]) {
            tmp3 = tmp3->upd(x, n - 1 - i);
            // if (x >= 5 && x <= 7) {
            //     //cout << "owo" << x << "," << i << endl;
            //     cout << tmp3->v << "," << tmp3->q(5, 7) << endl;
            // }
        }
        ac3[i] = tmp3;
    }
    //cout << "BRUH " << ac2[2]->q(5, 7) << "," << ac3[3]->q(5, 7) << endl;

    int holy[mx / magic][mx];
    for (int j = 0; j + magic <= m; j += magic) {
        int k = j / magic;
        bit die(n + 1);
        //cout << j << endl;
        for (int i = 0; i <= n; i++) die.u(i, i, i);
        for (int x = j; x < j + magic; x++) {
            int cur = 0;
            while (cur <= n) {
                if (1) {
                    int i = die.q(cur) / (n + 1);
                    int l = cur - 1, r = n + 1;
                    while (r - l > 1) {
                        int m = l + (r - l) / 2;
                        if (die.q(m) / (n + 1) == i) l = m;
                        else r = m;
                    }
                    //[cur, l] is bound
                    int l2 = cur - 1, r2 = l + 1;
                    while (r2 - l2 > 1) {
                        int m = l2 + (r2 - l2) / 2;
                        if (die.q(m) % (n + 1) <= a[x]) l2 = m;
                        else r2 = m;
                    }
                    //r is bound
                    die.u(cur, l2, 1);
                    cur = l + 1;
                }

                else {
                    if (die.q(cur) % (n + 1) <= a[x]) die.u(cur, cur, 1);
                    cur++;
                }
            }
            die.u(0, n, a[x] + 1);
            //for (int i = 0; i <= n; i++) cout << die.q(i) << ",";
            //cout << endl;
        }
        for (int i = 0; i <= n; i++) {
            if (i) die.a[i] += die.a[i - 1];
            holy[k][i] = die.a[i] % (n + 1);
        }
    }

    int q; cin >> q;

    while (q--) {
        int l, r; cin >> l >> r; l--;r--;
        //solve
        int li = -1, ri = n;
        int cur = l;
        auto qcnt = [&](int l, int r) {
            //cout << "q " << l << "," << r << "," << li << "," << ri << endl;
            int res = 0;
            if (l > r) return 0LL;
            if (r <= li) return r - l + 1;
            if (l >= ri) return 0LL;
            if (l <= li) {
                res += li - l + 1;
                l = li + 1;
            }
            if (r >= ri) r = ri - 1;
            //cout << "fk" << l << "," << r << "," << res << endl;
            return res + sm(l, r);
            //LMAO
        };

        auto qcnt2 = [&](int l, int r) {
            if (l > r) return 0LL;
            return (r - l + 1) - qcnt(l, r);};

        auto thing = [&](int t) { // should work for everything?
            //cout << "br" << t << endl;
            int a = qcnt(0, t - 1) * 2 + 1;
            int b = qcnt2(t + 1, n - 1) * 2;
            //if (b == 0) return;
            //cout << a << "|" << b << endl;
            if (a > b) {
                int ll = 0 - 1, rr = t + 1;
                while (rr - ll > 1) {
                    int m = ll + (rr - ll) / 2;
                    if (qcnt(m, t - 1) * 2 + 1 >= b)ll = m;
                    else rr = m;
                }
                ri = min(ri, ll);
                if (li >= ri) li = ri - 1;
            } else {
                int ll = t, rr = n;
                while (rr - ll > 1) {
                    int m = ll + (rr - ll) / 2;
                    //cout << ll << "," << rr << "," << m << endl;
                    if (qcnt2(t + 1, m) * 2 >= a)rr = m;
                    else ll = m;
                }
                li = rr;
                if (ri <= li) ri = li + 1;
            }
        };

        auto test = [&](int t) -> bool {
            //cout << "Bad" << t << endl;
            //cout << "how" << li << "," << ri << endl;
            int v1 = li == -1 ? 0 : ac2[li]->q(cur, t);
            //cout << "que" << endl;
            int v2 = ri == n ? 0 : ac3[ri]->q(cur, t);
            // cout << cur << "," << li << "," << ri << "," << t << "," << v1 << "," << v2 << endl;
             //cout << "nah" << endl;
            int tmp1 = prev(upper_bound(ls.begin(), ls.end(), li)) - ls.begin();
            int tmp2 = prev(upper_bound(rs.begin(), rs.end(), ri, greater<int>())) - rs.begin();
            if (tmp1 + v1 >= ls.size()) return false;
            if (tmp2 + v2 >= rs.size()) return false;
            int nl = v1 ? ls[tmp1 + v1] : li;
            int nr = v2 ? rs[tmp2 + v2] : ri;
            if (nl >= nr) return false;
            li = nl; ri = nr;
            cur = t + 1;
            return true;
        };

        while (cur <= r) {
            //cout << ac[cur]->q(li + 1, ri - 1) << endl;
            //cout << "die " << cur << "," << li + 1 << "," << ri - 1 << "," << r << endl;
            int t = min(ac[cur]->q(li + 1, ri - 1), r + 1);
            //do the thing?
            if (!test(t - 1)) break;
            //cout << "hi " << li << "," << ri << endl;
            //cout << "hell " << cur << "," << a[cur] << endl;
            //cout << "asdf " << li << "," << ri << "," << cur << endl;
            if (cur <= r)thing(a[cur++]);
            // cout << "asdf2 " << li << "," << ri << "," << cur << endl;
        }
        //cout << "asdf3 " << li << "," << ri << "," << cur << endl;
        //cout << "broke" << endl;
        if (cur <= r) {
            int t = min(ac[cur]->q(li + 1, ri - 1), r + 1);
            //cout << "T IS " << t << endl;
            for (int i = 18; i >= 0; i--) {
                if (cur + (1 << i) <= t - 1) test(cur + (1 << i));
            }
            //cout << "asdf4 " << li << "," << ri << "," << cur << endl;
            //if (cur <= r)cout << "no" << endl;
        }

        for (int i = 0; i < 5; i++) if (cur <= r) thing(a[cur++]);
        //cout << li << "," << ri << "," << cur << endl;
        while (cur <= r) {
            if (cur % magic == 0 && cur + magic <= r + 1) {
                //cout << cur << "," << magic << "," << ri << "," << holy[cur / magic][ri] << endl;
                ri = holy[cur / magic][ri];
                li = ri - 1;
                cur += magic;
            } else {
                //cout << "br" << "," << cur << "," << a[cur] << endl;
                if (a[cur] >= ri) ri++;
                ri += a[cur] + 1; ri %= (n + 1);
                li = ri - 1;
                cur++;
            }
            //cout << li << "," << ri << "," << cur << endl;
            //cout << ri << endl;
        }
        cout << qcnt(0, n - 1) << endl;
        //if (cur <= r)cout << "yes" << endl;
        //cout << li << "," << ri << endl;
        //if (cur <= r) cout << "ans: " << (li + ac2[n - 1]->q(cur, r)) % (n + 1) << endl;
        //else cout << "ans: " << qcnt(0, n - 1) << endl;
    }
}

Compilation message

Main.cpp: In member function 'void bit::u(long long int, long long int)':
Main.cpp:76:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     void u(int i, int v) { if (i < a.size()) a[i] += v; for (i++; i < b.size(); i += i & -i) b[i] += v; }
      |                                ~~^~~~~~~~~~
Main.cpp:76:69: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     void u(int i, int v) { if (i < a.size()) a[i] += v; for (i++; i < b.size(); i += i & -i) b[i] += v; }
      |                                                                   ~~^~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:246:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |             if (tmp1 + v1 >= ls.size()) return false;
      |                 ~~~~~~~~~~^~~~~~~~~~~~
Main.cpp:247:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |             if (tmp2 + v2 >= rs.size()) return false;
      |                 ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 817488 KB Output is correct
2 Correct 150 ms 817452 KB Output is correct
3 Correct 152 ms 817444 KB Output is correct
4 Correct 152 ms 817492 KB Output is correct
5 Correct 156 ms 817432 KB Output is correct
6 Correct 152 ms 817604 KB Output is correct
7 Correct 154 ms 817488 KB Output is correct
8 Correct 154 ms 817704 KB Output is correct
9 Correct 153 ms 817656 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 817488 KB Output is correct
2 Correct 150 ms 817452 KB Output is correct
3 Correct 152 ms 817444 KB Output is correct
4 Correct 152 ms 817492 KB Output is correct
5 Correct 156 ms 817432 KB Output is correct
6 Correct 152 ms 817604 KB Output is correct
7 Correct 154 ms 817488 KB Output is correct
8 Correct 154 ms 817704 KB Output is correct
9 Correct 153 ms 817656 KB Output is correct
10 Correct 173 ms 818436 KB Output is correct
11 Correct 162 ms 818256 KB Output is correct
12 Correct 164 ms 818256 KB Output is correct
13 Correct 164 ms 818364 KB Output is correct
14 Correct 164 ms 818260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 817488 KB Output is correct
2 Correct 150 ms 817452 KB Output is correct
3 Correct 152 ms 817444 KB Output is correct
4 Correct 152 ms 817492 KB Output is correct
5 Correct 156 ms 817432 KB Output is correct
6 Correct 152 ms 817604 KB Output is correct
7 Correct 154 ms 817488 KB Output is correct
8 Correct 154 ms 817704 KB Output is correct
9 Correct 153 ms 817656 KB Output is correct
10 Correct 173 ms 818436 KB Output is correct
11 Correct 162 ms 818256 KB Output is correct
12 Correct 164 ms 818256 KB Output is correct
13 Correct 164 ms 818364 KB Output is correct
14 Correct 164 ms 818260 KB Output is correct
15 Correct 154 ms 817604 KB Output is correct
16 Correct 153 ms 817492 KB Output is correct
17 Correct 153 ms 817492 KB Output is correct
18 Correct 690 ms 829332 KB Output is correct
19 Correct 736 ms 829808 KB Output is correct
20 Correct 794 ms 829852 KB Output is correct
21 Correct 869 ms 830876 KB Output is correct
22 Correct 753 ms 829444 KB Output is correct
23 Correct 769 ms 830000 KB Output is correct
24 Correct 650 ms 829344 KB Output is correct
25 Correct 648 ms 829356 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 817712 KB Output is correct
2 Correct 2562 ms 821516 KB Output is correct
3 Correct 2571 ms 821556 KB Output is correct
4 Correct 1559 ms 821144 KB Output is correct
5 Correct 1657 ms 821328 KB Output is correct
6 Correct 1266 ms 821512 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 817712 KB Output is correct
2 Correct 2562 ms 821516 KB Output is correct
3 Correct 2571 ms 821556 KB Output is correct
4 Correct 1559 ms 821144 KB Output is correct
5 Correct 1657 ms 821328 KB Output is correct
6 Correct 1266 ms 821512 KB Output is correct
7 Correct 158 ms 817904 KB Output is correct
8 Correct 157 ms 817656 KB Output is correct
9 Correct 153 ms 817748 KB Output is correct
10 Correct 160 ms 818260 KB Output is correct
11 Execution timed out 3045 ms 830936 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 817712 KB Output is correct
2 Correct 2562 ms 821516 KB Output is correct
3 Correct 2571 ms 821556 KB Output is correct
4 Correct 1559 ms 821144 KB Output is correct
5 Correct 1657 ms 821328 KB Output is correct
6 Correct 1266 ms 821512 KB Output is correct
7 Correct 155 ms 817492 KB Output is correct
8 Correct 153 ms 817492 KB Output is correct
9 Correct 154 ms 817492 KB Output is correct
10 Correct 161 ms 817488 KB Output is correct
11 Correct 151 ms 817668 KB Output is correct
12 Correct 152 ms 817552 KB Output is correct
13 Correct 152 ms 817492 KB Output is correct
14 Correct 157 ms 817748 KB Output is correct
15 Correct 153 ms 817488 KB Output is correct
16 Correct 154 ms 817468 KB Output is correct
17 Correct 164 ms 818232 KB Output is correct
18 Correct 684 ms 829232 KB Output is correct
19 Execution timed out 3047 ms 829280 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 817488 KB Output is correct
2 Correct 150 ms 817452 KB Output is correct
3 Correct 152 ms 817444 KB Output is correct
4 Correct 152 ms 817492 KB Output is correct
5 Correct 156 ms 817432 KB Output is correct
6 Correct 152 ms 817604 KB Output is correct
7 Correct 154 ms 817488 KB Output is correct
8 Correct 154 ms 817704 KB Output is correct
9 Correct 153 ms 817656 KB Output is correct
10 Correct 173 ms 818436 KB Output is correct
11 Correct 162 ms 818256 KB Output is correct
12 Correct 164 ms 818256 KB Output is correct
13 Correct 164 ms 818364 KB Output is correct
14 Correct 164 ms 818260 KB Output is correct
15 Correct 154 ms 817604 KB Output is correct
16 Correct 153 ms 817492 KB Output is correct
17 Correct 153 ms 817492 KB Output is correct
18 Correct 690 ms 829332 KB Output is correct
19 Correct 736 ms 829808 KB Output is correct
20 Correct 794 ms 829852 KB Output is correct
21 Correct 869 ms 830876 KB Output is correct
22 Correct 753 ms 829444 KB Output is correct
23 Correct 769 ms 830000 KB Output is correct
24 Correct 650 ms 829344 KB Output is correct
25 Correct 648 ms 829356 KB Output is correct
26 Correct 156 ms 817712 KB Output is correct
27 Correct 2562 ms 821516 KB Output is correct
28 Correct 2571 ms 821556 KB Output is correct
29 Correct 1559 ms 821144 KB Output is correct
30 Correct 1657 ms 821328 KB Output is correct
31 Correct 1266 ms 821512 KB Output is correct
32 Correct 158 ms 817904 KB Output is correct
33 Correct 157 ms 817656 KB Output is correct
34 Correct 153 ms 817748 KB Output is correct
35 Correct 160 ms 818260 KB Output is correct
36 Execution timed out 3045 ms 830936 KB Time limit exceeded
37 Halted 0 ms 0 KB -