Submission #1182624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182624		jerzyk	Modern Machine (JOI23_ho_t5)	C++20	25 / 100	3095 ms	76908 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<17;
string wzo;
int s0[N], s1[N];
int tab[N];
ll il0[N], il1[N];
int mi[N][20], ma[N][20];
int r0[N], r1[N];
vector<pair<pair<int, int>, int>> drz[2 * N];
vector<int> wh[2];
int bs0[N], bs1[N];

inline void LiczBS(int n)
{
    bs0[0] = 0; bs1[n + 1] = (int)wh[1].size() - 1;
    for(int i = 1; i <= n; ++i)
    {
        bs0[i] = bs0[i - 1];
        while(bs0[i] < (int)wh[0].size() - 1 && wh[0][bs0[i] + 1] <= i)
            ++bs0[i];
    }
    for(int i = n; i >= 1; --i)
    {
        bs1[i] = bs1[i + 1];
        while(bs1[i] > 0 && wh[1][bs1[i] - 1] >= i)
            --bs1[i];
    }
}

inline void LiczR(int n)
{
    for(int i = 1; i <= n + 1; ++i)
    {
        r1[i] = i;
        if(wzo[i - 1] == '<') r1[i] = r1[i - 1];
    }
    r0[n] = n;
    for(int i = n - 1; i >= 0; --i)
    {
        r0[i] = i;
        if(wzo[i + 1] == '>') r0[i] = r0[i + 1];
    }
}

void LiczRMQ(int n)
{
    for(int i = n; i >= 1; --i)
        for(int j = 1; i + (1<<j) - 1 <= n; ++j)
        {
            mi[i][j] = min(mi[i][j - 1], mi[i + (1<<(j - 1))][j - 1]);
            ma[i][j] = max(ma[i][j - 1], ma[i + (1<<(j - 1))][j - 1]);
        }
}

int MiQ(int a, int b)
{
    int d = (b - a + 1);
    int j = 31 - __builtin_clz(d);
    return min(mi[a][j], mi[b - (1<<j) + 1][j]);
}

int MaQ(int a, int b)
{
    int d = (b - a + 1);
    int j = 31 - __builtin_clz(d);
    return max(ma[a][j], ma[b - (1<<j) + 1][j]);
}

bool Int(pair<int, int> a, pair<int, int> b)
{
    return (max(a.st, b.st) <= min(a.nd, b.nd));
}

pair<int, int> GInt(pair<int, int> a, pair<int, int> b)
{
    return make_pair(max(a.st, b.st), min(a.nd, b.nd));
}

void Calc(int v, int n)
{
    int s1 = v * 2, s2 = v * 2 + 1;
    ++n;
    if(drz[s1].size() == 0 || drz[s2].size() == 0) return;
    //cerr << "CalcB " << s1 - N << " " << s2 - N << "\n";
    vector<pair<pair<int, int>, int>> akt;
    int m = drz[s2].size();
    int j = 0;
    for(int i = 0; i < (int)drz[s1].size(); ++i)
    {
        int l = (drz[s1][i].st.st + drz[s1][i].nd) % n, r = (drz[s1][i].st.nd + drz[s1][i].nd) % n;
        vector<pair<int, int>> nw;
        if(l <= r)
            nw.pb(make_pair(l, r));
        else
        {
            nw.pb(make_pair(l, n - 1));
            nw.pb(make_pair(0, r));
        }
        for(int l = 0; l < (int)nw.size(); ++l)
        {
        //if(nw[l].st < drz[s2][j].st.st) j = 0;
        //cout << "\n" << i << " " << "NW: " << nw[l].st << " " << nw[l].nd << "\n";
        while(!Int(nw[l], drz[s2][j].st) || GInt(nw[l], drz[s2][j].st).st != nw[l].st)
        {
            //cerr << nw[l].st << " " << nw[l].nd << "XD\n";
            j = (j + 1) % m;
        }
        while(j < m && Int(nw[l], drz[s2][j].st))
        {
            pair<int, int> it = GInt(nw[l], drz[s2][j].st);
            //cerr << j << " IT: " << it.st << " " << it.nd << "\n";
            it.st = (it.st - drz[s1][i].nd + n) % n;
            it.nd = (it.nd - drz[s1][i].nd + n) % n;
            akt.pb(make_pair(it, (drz[s1][i].nd + drz[s2][j].nd) % n));
            ++j;
        }
        j = (j - 1 + m) % m;
        }
    }
    if((int)akt.size() > 0)
        drz[v].pb(akt[0]);
    for(int i = 1; i < (int)akt.size(); ++i)
    {
        if(akt[i].nd == drz[v].back().nd)
            drz[v].back().st.nd = akt[i].st.nd;
        else
            drz[v].pb(akt[i]);
    }
    //if(drz[v].back().st.nd != n - 1)
        //cout << drz[v].back().st.nd << " " << "Dupa XD\n";
    //for(int i = 0; i < (int)drz[v].size(); ++i)
        //cout << "R: " << drz[v][i].st.st << " " << drz[v][i].st.nd << " " << drz[v][i].nd << "\n";
    //cout << "CalcE\n";
}

int F(int v, int x)
{
    int pos = (upper_bound(drz[v].begin(), drz[v].end(), make_pair(make_pair(x + 1, 0), 0)) - drz[v].begin()) - 1;
    x += drz[v][pos].nd;
    return x;
}

int Query(int a, int b, int bas, int n)
{
    a += N - 1; b += N + 1;
    vector<int> q;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0)
            bas = F(a + 1, bas) % (n + 1);
        if(b % 2 == 1)
            q.pb(b - 1);
        a /= 2; b /= 2;
    }
    for(int i = (int)q.size() - 1; i >= 0; --i)
        bas = F(q[i], bas) % (n + 1);
    return bas;
}

bool Check(int a, int x, int l, int r, int p0, int p1)
{
    if(MiQ(a, x) < r) return 0;
    if(MaQ(a, x) > l) return 0;
    ll d0 = il0[x] - il0[a - 1];
    ll d1 = il1[x] - il1[a - 1];
    if((ll)p0 + (ll)d0 >= (int)wh[0].size()) return 0;
    if((ll)p1 - (ll)d1 < 0) return 0;
    if(max(l, wh[0][p0 + d0]) >= min(r, wh[1][p1 - d1])) return 0;
    return 1;
}

void Upd(int a, int x, int &l, int &r, int &p0, int &p1)
{
    ll d0 = il0[x] - il0[a - 1];
    ll d1 = il1[x] - il1[a - 1];
    p0 += d0; p1 -= d1;
    l = wh[0][p0]; r = wh[1][p1];
}

void Manual(int n, int pos, int &l, int &r, int &p0, int &p1)
{
    int lew = 0, pr = 0;
    if(pos <= l) lew = pos - 1;
    else lew = l + s1[min(pos, r) - 1] - s1[l];
    if(pos >= r) pr = n - pos;
    else pr = n - r + 1 + s0[r - 1] - s0[max(pos, l)];
    //cout << l << " " << r << " " << pos << " " << "Q: " << lew << " " << pr << "\n";
    if(lew < pr)
    {
        int del = lew + 1;
        int p2;
        int fr = 0;
        if(pos < r) fr = s0[r - 1] - s0[max(l, pos)];
        if(fr >= del)
        {
            //p2 = (upper_bound(wh[0].begin(), wh[0].end(), max(l, pos)) - wh[0].begin()) + del - 1;
            p2 = (bs0[max(l, pos)] + 1) + del - 1;
            l = wh[0][p2];
        }else
        {
            del -= fr;
            l = max(pos + 1, r) + del - 1;
            r = l + 1;
        }
    }else
    {
        int del = pr;
        int p2;
        int fr = 0;
        if(pos > l) fr = s1[min(pos, r) - 1] - s1[l];
        if(fr >= del)
        {
            //p2 = (lower_bound(wh[1].begin(), wh[1].end(), min(r, pos)) - wh[1].begin()) - del;
            p2 = (bs1[min(r, pos)]) - del;
            //cout << "p2: " << wh[1][p2] << "\n";
            r = min(wh[1][p2], pos);
            l = min(l, r - 1);
        }else
        {
            del -= fr;
            r = min(pos - 1, l) - del + 1;
            l = r - 1;
        }
    }
    p0 = bs0[l];
    p1 = bs1[r];
    //p0 = (upper_bound(wh[0].begin(), wh[0].end(), l) - wh[0].begin()) - 1;
    //p1 = (lower_bound(wh[1].begin(), wh[1].end(), r) - wh[1].begin());
    //cout << l << " " << r << " " << wh[0][p0] << " " << wh[1][p1] << "\n";
}

int BS(int a, int b, int l, int r, int p0, int p1)
{
    int p = a - 1, k = b, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Check(a, s, l, r, p0, p1))
            p = s;
        else
            k = s - 1;
    }
    return p;
}

void Rozszerz(int &l, int &r, int &p0, int &p1)
{
    l = min(r - 1, r0[l]);
    r = max(l + 1, r1[r]);
}

int DoA(int n, int a, int b)
{
    int l = 0, r = n + 1;
    int p0 = 0, p1 = (int)wh[1].size() - 1;

    while(a <= b)
    {
        Rozszerz(l, r, p0, p1);
        int nxt = BS(a, b, l, r, p0, p1);
        //cout << a << " " << b << " " << nxt << "\n";
        //cout << "B: " << l << " " << r << " " << p0 << " " << p1 << "\n";
        Upd(a, nxt, l, r, p0, p1);
        Rozszerz(l, r, p0, p1);
        //cout << "A: " << l << " " << r << " " << p0 << " " << p1 << "\n";
        a = nxt + 1;
        if(a <= b)
        {
            Manual(n, tab[a], l, r, p0, p1);
            ++a;
        }
        if(a <= b && l == r - 1)
        {
            return Query(a, b, l, n);
        }
        Rozszerz(l, r, p0, p1);
    }
    return l + s1[r - 1] - s1[l];
}

void Solve()
{
    int n, m, q;
    cin >> n >> m;
    cin >> wzo;
    wzo = '#' + wzo;
    LiczR(n);
    wh[0].pb(0);
    for(int i = 1; i <= n; ++i)
    {
        if(wzo[i] == 'B')
        {
            ++s0[i];
            wh[0].pb(i);
        }
        else
        {
            ++s1[i];
            wh[1].pb(i);
        }
        s0[i] += s0[i - 1]; s1[i] += s1[i - 1];
    }
    s0[n + 1] += s0[n]; s1[n + 1] += s1[n];
    wh[1].pb(n + 1);
    for(int i = 1; i <= m; ++i)
    {
        cin >> tab[i];
        mi[i][0] = II; ma[i][0] = 0;
        if(tab[i] <= (n / 2))
        {
            ma[i][0] = tab[i];
            il0[i] += tab[i];
        }
        else
        {
            mi[i][0] = tab[i];
            il1[i] += (n - tab[i]);
        }
        il0[i] += il0[i - 1];
        il1[i] += il1[i - 1];

        drz[i + N].pb(make_pair(make_pair(0, tab[i] - 1), tab[i] + 1));
        drz[i + N].pb(make_pair(make_pair(tab[i], n), tab[i]));
    }
    LiczBS(n);
    LiczRMQ(n);
    for(int i = N - 1; i >= 1; --i)
        Calc(i, n);
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        int a, b;
        cin >> a >> b;
        int ans = DoA(n, a, b);
        //int ans = Query(a, b, bas, n);
        cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

• 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