Submission #931564

#	Time	Username	Problem	Language	Result	Execution time	Memory
931564		Pring	Modern Machine (JOI23_ho_t5)	C++17	25 / 100	467 ms	17236 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 120005;
int n, m, q, a[MXN];
string s;

inline int f(int x) {
    return n - x - 1;
}

struct SMG {
    int val[MXN * 4], tag[MXN * 4];
    void add_tag(int id, int l, int r, int _t) {
        val[id] = (r - l) * _t;
        tag[id] = _t;
    }
    void push(int id, int l, int r) {
        if (tag[id] == -1) return;
        int mid = (l + r) >> 1;
        add_tag(id * 2 + 1, l, mid, tag[id]);
        add_tag(id * 2 + 2, mid, r, tag[id]);
        tag[id] = -1;
    }
    void pull(int id) {
        val[id] = val[id * 2 + 1] + val[id * 2 + 2];
    }
    void build(int id, int l, int r, string &s, char tg) {
        tag[id] = -1;
        if (l + 1 == r) {
            val[id] = (s[l] == tg);
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2 + 1, l, mid, s, tg);
        build(id * 2 + 2, mid, r, s, tg);
        pull(id);
    }
    void modify(int id, int l, int r, int _l, int _r, int v) {
        if (_r <= l || r <= _l) return;
        if (_l <= l && r <= _r) {
            add_tag(id, l, r, v);
            return;
        }
        int mid = (l + r) >> 1;
        push(id, l, r);
        modify(id * 2 + 1, l, mid, _l, _r, v);
        modify(id * 2 + 2, mid, r, _l, _r, v);
        pull(id);
    }
    int query(int id, int l, int r, int _l, int _r) {
        if (_r <= l || r <= _l) return 0;
        if (_l <= l && r <= _r) return val[id];
        int mid = (l + r) >> 1;
        push(id, l, r);
        return query(id * 2 + 1, l, mid, _l, _r) + query(id * 2 + 2, mid, r, _l, _r);
    }
    int BSH(int id, int l, int r, int b) {
        // debug(l, r, b);
        if (l + 1 == r) return l;
        int mid = (l + r) >> 1;
        push(id, l, r);
        return (val[id * 2 + 1] >= b ? BSH(id * 2 + 1, l, mid, b) : BSH(id * 2 + 2, mid, r, b - val[id * 2 + 1]));
    }
} smg[2];

void INIT() {
    smg[0].build(0, 0, n, s, 'B');
    reverse(s.begin(), s.end());
    smg[1].build(0, 0, n, s, 'R');
    reverse(s.begin(), s.end());
}

void FLAT(int l, int r, char c) {
    int x = (c == 'B');
    smg[0].modify(0, 0, n, l, r, x);
    smg[1].modify(0, 0, n, f(r) + 1, f(l) + 1, 1 - x);
}

void DO(int sr) {
    // debug(sr);
    int nb = smg[0].query(0, 0, n, sr + 1, n), nr = smg[1].query(0, 0, n, f(sr) + 1, n);
    if (nb > nr) {
        debug(1);
        // debug(nr + 1 + smg[0].query(0, 0, n, 0, sr));
        int id = smg[0].BSH(0, 0, n, nr + 1 + smg[0].query(0, 0, n, 0, sr + 1));
        // debug(id);
        FLAT(0, id + 1, 'R');
    } else {
        if (nb == 0) {
            debug(2);
            FLAT(sr, n, 'B');
        } else {
            debug(3);
            int id = smg[1].BSH(0, 0, n, nb + smg[1].query(0, 0, n, 0, f(sr) + 1));
            debug(id);
            FLAT(f(id), n, 'B');
        }
    }
}

void miku() {
    int l, r;
    cin >> n >> m >> s;
    FOR(i, 1, m + 1) cin >> a[i];
    cin >> q;
    if (q > 5) return;
    while (q--) {
        INIT();
        cin >> l >> r;
        FOR(i, l, r + 1) {
            DO(a[i] - 1);
        }
        cout << smg[1].val[0] << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void DO(long long int)':
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:100:9: note: in expansion of macro 'debug'
  100 |         debug(1);
      |         ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:107:13: note: in expansion of macro 'debug'
  107 |             debug(2);
      |             ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:110:13: note: in expansion of macro 'debug'
  110 |             debug(3);
      |             ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:112:13: note: in expansion of macro 'debug'
  112 |             debug(id);
      |             ^~~~~

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