oj.uz

답안 #847966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847966 2023-09-10T23:57:45 Z resting Modern Machine (JOI23_ho_t5) C++17
15 / 100
 271 ms 886316 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 * 40]; 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 * 80]; 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;
                if (ri > n + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 885076 KB Output is correct
2 Correct 233 ms 885164 KB Output is correct
3 Correct 240 ms 885280 KB Output is correct
4 Correct 271 ms 885072 KB Output is correct
5 Correct 250 ms 885124 KB Output is correct
6 Correct 234 ms 885244 KB Output is correct
7 Correct 239 ms 885176 KB Output is correct
8 Correct 245 ms 885328 KB Output is correct
9 Correct 233 ms 885232 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 885076 KB Output is correct
2 Correct 233 ms 885164 KB Output is correct
3 Correct 240 ms 885280 KB Output is correct
4 Correct 271 ms 885072 KB Output is correct
5 Correct 250 ms 885124 KB Output is correct
6 Correct 234 ms 885244 KB Output is correct
7 Correct 239 ms 885176 KB Output is correct
8 Correct 245 ms 885328 KB Output is correct
9 Correct 233 ms 885232 KB Output is correct
10 Correct 247 ms 886316 KB Output is correct
11 Correct 252 ms 886096 KB Output is correct
12 Correct 247 ms 886096 KB Output is correct
13 Correct 247 ms 885840 KB Output is correct
14 Correct 245 ms 886096 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 885076 KB Output is correct
2 Correct 233 ms 885164 KB Output is correct
3 Correct 240 ms 885280 KB Output is correct
4 Correct 271 ms 885072 KB Output is correct
5 Correct 250 ms 885124 KB Output is correct
6 Correct 234 ms 885244 KB Output is correct
7 Correct 239 ms 885176 KB Output is correct
8 Correct 245 ms 885328 KB Output is correct
9 Correct 233 ms 885232 KB Output is correct
10 Correct 247 ms 886316 KB Output is correct
11 Correct 252 ms 886096 KB Output is correct
12 Correct 247 ms 886096 KB Output is correct
13 Correct 247 ms 885840 KB Output is correct
14 Correct 245 ms 886096 KB Output is correct
15 Correct 233 ms 885196 KB Output is correct
16 Incorrect 232 ms 885072 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 238 ms 885312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 238 ms 885312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 238 ms 885312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 885076 KB Output is correct
2 Correct 233 ms 885164 KB Output is correct
3 Correct 240 ms 885280 KB Output is correct
4 Correct 271 ms 885072 KB Output is correct
5 Correct 250 ms 885124 KB Output is correct
6 Correct 234 ms 885244 KB Output is correct
7 Correct 239 ms 885176 KB Output is correct
8 Correct 245 ms 885328 KB Output is correct
9 Correct 233 ms 885232 KB Output is correct
10 Correct 247 ms 886316 KB Output is correct
11 Correct 252 ms 886096 KB Output is correct
12 Correct 247 ms 886096 KB Output is correct
13 Correct 247 ms 885840 KB Output is correct
14 Correct 245 ms 886096 KB Output is correct
15 Correct 233 ms 885196 KB Output is correct
16 Incorrect 232 ms 885072 KB Output isn't correct
17 Halted 0 ms 0 KB -