oj.uz

Submission #847925

# Submission time Handle Problem Language Result Execution time Memory
847925 2023-09-10T22:05:39 Z resting Modern Machine (JOI23_ho_t5) C++17
15 / 100
 241 ms 359940 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int magic = 350;
//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 * 18]; 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 * 18]; 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() {
    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[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) {
                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]) r2 = m;
                    else l2 = m;
                }
                //r is bound
                die.u(r2, l, 1);
                cur = l + 1;
            }
            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;
            //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;
            if (ls[tmp1 + v1] >= rs[tmp2 + v2]) return false;
            if (v1)li = ls[tmp1 + v1];
            if (v2)ri = rs[tmp2 + v2];
            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 + i <= t - 1) test(cur + i);
            }
            //cout << "asdf4 " << li << "," << ri << "," << cur << endl;
            //if (cur <= r)cout << "no" << endl;
        }

        if (cur <= r) thing(a[cur++]);
        //cout << li << "," << ri << "," << cur << endl;
        while (cur <= r) {
            if (0 && 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 if (1) {
                int v = ri;
                int was = li;
                int v2 = v; if (a[cur] >= ri) v++;
                v += a[cur] + 1; v %= (n + 1);
                thing(a[cur++]);
                if (v != ri) {
                    //cout << "BAD: " << li<<","<< v2 << "," << a[cur - 1] << ","<<li<<","<<ri<<","<<v<< endl;
                }
            } 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:237: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]
  237 |             if (tmp1 + v1 >= ls.size()) return false;
      |                 ~~~~~~~~~~^~~~~~~~~~~~
Main.cpp:238: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]
  238 |             if (tmp2 + v2 >= rs.size()) return false;
      |                 ~~~~~~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:280:21: warning: unused variable 'was' [-Wunused-variable]
  280 |                 int was = li;
      |                     ^~~
Main.cpp:281:21: warning: unused variable 'v2' [-Wunused-variable]
  281 |                 int v2 = v; if (a[cur] >= ri) v++;
      |                     ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 169296 KB Output is correct
2 Correct 24 ms 169360 KB Output is correct
3 Correct 24 ms 169452 KB Output is correct
4 Correct 23 ms 169296 KB Output is correct
5 Correct 25 ms 169296 KB Output is correct
6 Correct 23 ms 169308 KB Output is correct
7 Correct 25 ms 169300 KB Output is correct
8 Correct 26 ms 169296 KB Output is correct
9 Correct 24 ms 169308 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 169296 KB Output is correct
2 Correct 24 ms 169360 KB Output is correct
3 Correct 24 ms 169452 KB Output is correct
4 Correct 23 ms 169296 KB Output is correct
5 Correct 25 ms 169296 KB Output is correct
6 Correct 23 ms 169308 KB Output is correct
7 Correct 25 ms 169300 KB Output is correct
8 Correct 26 ms 169296 KB Output is correct
9 Correct 24 ms 169308 KB Output is correct
10 Correct 35 ms 170064 KB Output is correct
11 Correct 36 ms 170328 KB Output is correct
12 Correct 38 ms 170320 KB Output is correct
13 Correct 34 ms 170072 KB Output is correct
14 Correct 35 ms 170064 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 169296 KB Output is correct
2 Correct 24 ms 169360 KB Output is correct
3 Correct 24 ms 169452 KB Output is correct
4 Correct 23 ms 169296 KB Output is correct
5 Correct 25 ms 169296 KB Output is correct
6 Correct 23 ms 169308 KB Output is correct
7 Correct 25 ms 169300 KB Output is correct
8 Correct 26 ms 169296 KB Output is correct
9 Correct 24 ms 169308 KB Output is correct
10 Correct 35 ms 170064 KB Output is correct
11 Correct 36 ms 170328 KB Output is correct
12 Correct 38 ms 170320 KB Output is correct
13 Correct 34 ms 170072 KB Output is correct
14 Correct 35 ms 170064 KB Output is correct
15 Correct 25 ms 169520 KB Output is correct
16 Correct 23 ms 169296 KB Output is correct
17 Correct 25 ms 169296 KB Output is correct
18 Runtime error 196 ms 359940 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 169396 KB Output is correct
2 Runtime error 241 ms 350212 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 169396 KB Output is correct
2 Runtime error 241 ms 350212 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 169396 KB Output is correct
2 Runtime error 241 ms 350212 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 169296 KB Output is correct
2 Correct 24 ms 169360 KB Output is correct
3 Correct 24 ms 169452 KB Output is correct
4 Correct 23 ms 169296 KB Output is correct
5 Correct 25 ms 169296 KB Output is correct
6 Correct 23 ms 169308 KB Output is correct
7 Correct 25 ms 169300 KB Output is correct
8 Correct 26 ms 169296 KB Output is correct
9 Correct 24 ms 169308 KB Output is correct
10 Correct 35 ms 170064 KB Output is correct
11 Correct 36 ms 170328 KB Output is correct
12 Correct 38 ms 170320 KB Output is correct
13 Correct 34 ms 170072 KB Output is correct
14 Correct 35 ms 170064 KB Output is correct
15 Correct 25 ms 169520 KB Output is correct
16 Correct 23 ms 169296 KB Output is correct
17 Correct 25 ms 169296 KB Output is correct
18 Runtime error 196 ms 359940 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -