Submission #950565

#	Time	Username	Problem	Language	Result	Execution time	Memory
950565		peterandvoi	Modern Machine (JOI23_ho_t5)	C++17	100 / 100	989 ms	239460 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 120005;

int n, m, q;
char c[N];
int a[N];

struct from_to {
    int l, L, len;

    from_to(): l(0), L(0), len(0) {};

    from_to(int l, int L, int len): l(l), L(L), len(len) {};

    int r() const {
        return l + len - 1;
    }

    bool operator < (const from_to &oth) const {
        return l < oth.l;
    }
};

int add(int a, int b) {
    a += b;
    while (a >= n + 1) {
        a -= n + 1;
    }
    return a;
}

vector<from_to> tree[N << 2];

vector<from_to> cmb(const vector<from_to> &a, const vector<from_to> &b) {
    vector<from_to> res;
    for (auto [bl, al, len] : a) {
        int ar = add(al, len - 1);
        int br = add(bl, len - 1);
        int L = lower_bound(b.begin(), b.end(), from_to(al + 1, 0, 0)) - b.begin() - 1;
        int R = lower_bound(b.begin(), b.end(), from_to(ar + 1, 0, 0)) - b.begin() - 1;
        R += al > ar ? (int) b.size() : 0;
        for (int i = L; i <= R; ++i) {
            int j = i % (int) b.size();
            int delta = max(b[j].l, al) - b[j].l;
            int len = min(br - bl + 1, b[j].r() - max(b[j].l, al) + 1);
            int tl = add(b[j].L, delta);
            res.emplace_back(bl, tl, len);
            bl += len;
            al = add(al, len);
        }
    }
    return res;
}

void bld(int id, int l, int r) {
    if (l == r) {
        tree[id].emplace_back(0, add(0, a[l] + 1), a[l]);
        tree[id].emplace_back(a[l], add(a[l], a[l]), n - a[l] + 1);
    } else {
        int mid = l + r >> 1;
        bld(id << 1, l, mid);
        bld(id << 1 | 1, mid + 1, r);
        tree[id] = cmb(tree[id << 1], tree[id << 1 | 1]);
    }
}

int get(const vector<from_to> &a, int p) {
    int pos = lower_bound(a.begin(), a.end(), from_to(p + 1, 0, 0)) - a.begin() - 1;
    return add(a[pos].L, p - a[pos].l);
}

int qry(int u, int v, int p, int id = 1, int l = 1, int r = m) {
    if (u <= l && r <= v) {
        return get(tree[id], p);
    }
    int mid = l + r >> 1;
    if (u <= mid && mid < v) {
        return qry(u, v, qry(u, v, p, id << 1, l, mid), id << 1 | 1, mid + 1, r);
    }
    if (mid < u) {
        return qry(u, v, p, id << 1 | 1, mid + 1, r);
    }
    return qry(u, v, p, id << 1, l, mid);
}

const int LOG = 18;

int numB, numR;
int cnt_red[N];
int MASK[LOG];
int red[N], blue[N];
int jump[LOG][LOG][N];
int pushB[LOG][N], pushR[LOG][N];

int get(int l, int r, int pref[N]) {
    return pref[r] - pref[l - 1];
}

bool ck(int l, int r, int pos) {
    return red[r] <= pos || (blue[l] < pos && c[pos] == 'B');
}

int get_red(int l, int r, int pos) {
    int cnt = blue[l] + get(blue[l], red[r] - 1, cnt_red);
    if (pos != -1) {
        cnt = add(cnt, pos + ck(l, r, pos));
    }
    return cnt;
}

int qry(int l, int r) {
    int L = 0, R = 0, x = 0, y = 0;
    int iter = 2 * LOG;
    while (iter--) {
        int nxt = min(r + 1, jump[x][y][l]);
        if (l < nxt) {
            auto check = [&](int mid) {
                int tL = min(numB + 1, L + get(l, mid, pushB[x]));
                int tR = min(numR + 1, R + get(l, mid, pushR[y]));
                return blue[tL] < red[tR];
            };
            if (check(nxt - 1)) {
                L += get(l, nxt - 1, pushB[x]);
                R += get(l, nxt - 1, pushR[y]);
                l = nxt;
            } else {
                int tl = l, tr = nxt - 2, p = l - 1;
                while (tl <= tr) {
                    int mid = tl + tr >> 1;
                    if (check(mid)) {
                        p = mid;
                        tl = mid + 1;
                    } else {
                        tr = mid - 1;
                    }
                }
                L += get(l, p, pushB[x]);
                R += get(l, p, pushR[y]);
                int cnt = get_red(L, R, a[p + 1]);
                return p + 2 > r ? cnt : qry(p + 2, r, cnt);
            }
        }
        int num_red = get_red(L, R, -1);
        if (l == r + 1) {
            return num_red;
        }
        bool spec = ck(L, R, a[l]);
        int tl = L, tr = R;
        if (a[l] <= n - num_red) {
            tl = min(numB + 1, L + a[l] + spec);
        } else {
            tr = min(numR + 1, R + n - a[l] + !spec);
        }
        if (blue[tl] + 1 >= red[tr]) {
            int cnt = get_red(L, R, a[l]);
            return l + 1 > r ? cnt : qry(l + 1, r, cnt);
        }
        L = tl;
        R = tr;
        l++;
        while (x + 1 < LOG && MASK[x + 1] <= blue[L]) {
            x++;
        }
        while (y + 1 < LOG && red[R] <= n - MASK[y + 1] + 1) {
            y++;
        }
    }
    assert(0);
    return -1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 1; i < LOG; ++i) {
        MASK[i] = 1 << (i - 1);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        cnt_red[i] = cnt_red[i - 1] + (c[i] == 'R');
        if (c[i] == 'B') {
            blue[++numB] = i;
        }
    }
    cnt_red[n + 1] = cnt_red[n];
    blue[numB + 1] = n + 1;
    red[0] = n + 1;
    for (int i = n; i >= 1; --i) {
        if (c[i] == 'R') {
            red[++numR] = i;
        }
    }
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }
    bld(1, 1, m);
    cin >> q;
    for (int i = 0; i < LOG; ++i) {
        for (int j = 0; j < LOG; ++j) {
            jump[i][j][m + 1] = m + 1;;
            for (int k = m; k >= 1; --k) {
                bool edge_case = a[k] == n && c[n] == 'B';
                jump[i][j][k] = MASK[i] < a[k] && a[k] <= n - MASK[j] && !edge_case ? k : jump[i][j][k + 1];
            }
        }
    }
    for (int i = 0; i < LOG; ++i) {
        for (int j = 1; j <= m; ++j) {
            pushB[i][j] = pushB[i][j - 1];
            pushR[i][j] = pushR[i][j - 1];
            if (a[j] <= MASK[i]) {
                pushB[i][j] += a[j];
            }
            if (n - MASK[i] < a[j]) {
                pushR[i][j] += n - a[j];
            }
        }
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << qry(l, r) << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'void bld(int, int, int)':
Main.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int qry(int, int, int, int, int, int)':
Main.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int qry(int, int)':
Main.cpp:138:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |                     int mid = tl + tr >> 1;
      |                               ~~~^~~~

• Subtask 1: 3 / 3
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 26 / 26
• Subtask 6: 17 / 17
• Subtask 7: 21 / 21