Submission #1189227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189227		niepamietamhasla	Modern Machine (JOI23_ho_t5)	C++20	100 / 100	2766 ms	78708 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int n, m;
string s;

struct c{
    int a;
    int b;
    int dod;
};

struct d{
    vector<c> swapy;
};

vector<int> krasnoludki;

const int MAXN = 2e5 + 5;
const int base = 1 << 17;
int ans[MAXN];
d drugaczesc[2 * base];
int M;

bool comp(const c &c1, const c &c2){
    if(c1.a != c2.a){
        return c1.a < c2.a;
    }
    return false;
}

int a, b;


int drugiwyn(int w, int akt_a, int akt_b, int curr){
    if(a > b) return curr;
    if(a <= akt_a and akt_b <= b){
        int p = 0;
        int k = drugaczesc[w].swapy.size() - 1;
        while(p != k){
            int sr = (p + k) / 2;
            if(drugaczesc[w].swapy[sr].b < curr){
                p = sr + 1;
            }
            else{
                k = sr;
            }
        }
        return (curr + drugaczesc[w].swapy[p].dod) % M;
    }
    if(akt_a > b or akt_b < a) return curr;
    int mid = (akt_a + akt_b) / 2;
    curr = drugiwyn(2 * w, akt_a, mid, curr);
    curr = drugiwyn(2 * w + 1, mid + 1, akt_b, curr);
    return curr;
}

struct e{
    int sR;
    int sB;
};

e strzalki[2 * base];

int iloscR(int w, int akt_a, int akt_b){
    if(a > b) return 0;
    if(a <= akt_a and akt_b <= b){
        return strzalki[w].sR;
    }
    if(akt_a > b or akt_b < a) return 0;
    int mid = (akt_a + akt_b) / 2;
    return iloscR(2 * w, akt_a, mid) + iloscR(2 * w + 1, mid + 1, akt_b);
}

int iloscB(int w, int akt_a, int akt_b){
    if(a > b) return 0;
    if(a <= akt_a and akt_b <= b){
        return strzalki[w].sB;
    }
    if(akt_a > b or akt_b < a) return 0;
    int mid = (akt_a + akt_b) / 2;
    return iloscB(2 * w, akt_a, mid) + iloscB(2 * w + 1, mid + 1, akt_b);
}

int ktaB(int w, int akt_a, int akt_b, int curr, int cel){
    if(akt_a == akt_b) return akt_a;
    int mid = (akt_a + akt_b) / 2;
    if(strzalki[2 * w].sB + curr < cel){
        return ktaB(2 * w + 1, mid + 1, akt_b, curr + strzalki[2 * w].sB, cel);
    }
    else{
        return ktaB(2 * w, akt_a, mid, curr, cel);
    }
}

int ktaR(int w, int akt_a, int akt_b, int curr, int cel){
    if(akt_a == akt_b) return akt_a;
    int mid = (akt_a + akt_b) / 2;
    if(strzalki[2 * w + 1].sR + curr < cel){
        return ktaR(2 * w, akt_a, mid, curr + strzalki[2 * w + 1].sR, cel);
    }
    else{
        return ktaR(2 * w + 1, mid + 1, akt_b, curr, cel);
    }
}

pair<int,int> dodajp(int pref, int suff, int ile, int n){
    int pocz = pref;
    int kon = n - suff + 1;
    a = pocz + 1;
    b = kon - 1;
    int v = iloscB(1, 1, base);
    if(ile >= v){
        pocz = kon - 1;
        ile -= v;
        pocz = (pocz + ile) % M;
        kon = pocz + 1;
        return {pocz, n - pocz};
    }
    a = 1;
    b = pocz;
    v = iloscB(1, 1, base);
    return {ktaB(1, 1, base, 0, v + ile + 1) - 1, suff};
}

pair<int,int> dodajk(int pref, int suff, ll ile, int n){
    int pocz = pref;
    int kon = n - suff + 1;
    a = pocz + 1;
    b = kon - 1;
    int v = iloscR(1, 1, base);
    //cout << pocz << " " << kon << " pk\n";
    //cout << ile << " " << v << " il\n";
    if(ile >= v){
        //cout << suff << " " << ile + 1 << " si\n";
        ile -= v;
        //cout << pocz << " " << ile << " pi\n";
        pocz = (pocz - ile + 2 * M) % M;
        return {pocz, n - pocz};
    }
    a = kon;
    b = base;
    v = iloscR(1, 1, base);
    return {pocz, n - ktaR(1, 1, base, 0, v + ile + 1)};
}

pair<int,int> dodajs(int pref, int suff, int mid, int n){
    int pocz = pref;
    int kon = n - suff + 1;
    int iR1 = pref;
    a = pocz + 1;
    b = mid - 1;
    int iR2 = iloscR(1, 1, base);
    int iB1 = suff;
    a = mid + 1;
    b = kon - 1;
    int iB2 = iloscB(1, 1, base);
    int s1 = iR1 + iR2;
    int s2 = iB1 + iB2;
    //cout << s1 << " " << s2 << " s\n";
    //cout << iB1 << " " << iB2 << " iB\n";
    if(s1 >= s2){
        if(s2 >= iR2){
            pocz = pref - (s2 - iR2);
            return {pocz, n - pocz};
        }
        else{
            a = mid;
            b = base;
            int v = iloscR(1, 1, base);
            return {pocz, n - ktaR(1, 1, base, 0, v + s2 + 1)};
        }
    }
    else{
        if(s1 + 1 >= iB2){
            pocz = kon - 1 + (s1 - iB2 + 1);
            return {pocz, n - pocz};
        }
        else{
            a = 1;
            b = mid;
            int v = iloscB(1, 1, base);
            return {ktaB(1, 1, base, 0, v + s1 + 2) - 1, suff};
        }
    }
}

struct zap{
    int pref;
    int suff;
    int org;
    int a;
    int b;
};

vector<zap> queries;
vector<zap> nowe;

struct d2{
    int sumaakt;
    int sumanieakt;
    int minimalny;
};

d2 drzew[2 * base];
vector<int> wylacz[MAXN];

const int INF = 1e9;

void cofnij(){
    for(int i = 1; i <= m; ++i){
        drzew[i + base - 1] = {n - krasnoludki[i], 0, krasnoludki[i]};
    }
    for(int i = base - 1; i > 0; --i){
        drzew[i].sumaakt = drzew[2 * i].sumaakt + drzew[2 * i + 1].sumaakt;
        drzew[i].sumanieakt = drzew[2 * i].sumanieakt + drzew[2 * i + 1].sumanieakt;
        drzew[i].minimalny = min(drzew[2 * i].minimalny, drzew[2 * i + 1].minimalny);
    }
    return;
}

bool comp2(const zap &z1, const zap &z2){
    if(z1.pref != z2.pref){
        return z1.pref < z2.pref;
    }
    return false;
}

void akt(int w){
    w += base - 1;
    drzew[w] = {0, krasnoludki[w - base + 1], INF};
    w /= 2;
    while(w != 0){
        drzew[w].sumaakt = drzew[2 * w].sumaakt + drzew[2 * w + 1].sumaakt;
        drzew[w].sumanieakt = drzew[2 * w].sumanieakt + drzew[2 * w + 1].sumanieakt;
        drzew[w].minimalny = min(drzew[2 * w].minimalny, drzew[2 * w + 1].minimalny);
        w /= 2;
    }
    return;
}

int znajdz(int w, int akt_a, int akt_b, int granica){
    if(akt_a == akt_b) return akt_a;
    int mid = (akt_a + akt_b) / 2;
    //cout << w << " " << drzew[2 * w].minimalny << " " << drzew[2 * w + 1].minimalny <<  " d\n";
    //cout << granica << " granica\n";
    if(drzew[2 * w].minimalny < granica){
        return znajdz(2 * w, akt_a, mid, granica);
    }
    else{
        return znajdz(2 * w + 1, mid + 1, akt_b, granica);
    }
    return -1;
}

int znajdzsrodek(int w, int a, int b, int akt_a, int akt_b, int granica){
    //cout << w << " " << a << " " << b << " " << akt_a << " " << akt_b << " " << granica << " drzewo\n";
    if(a <= akt_a and akt_b <= b){
        //cout << w << " " << drzew[w].minimalny << " " << granica << " oblsr\n";
        //cout << "#\n";
        //cout << drzew[w].minimalny << " " << granica << " gr\n";
        if(drzew[w].minimalny >= granica) return -1;
        else return znajdz(w, akt_a, akt_b, granica);
    }
    if(akt_a > b or akt_b < a) return -1;
    int mid = (akt_a + akt_b) / 2;
    int v1 = znajdzsrodek(2 * w, a, b, akt_a, mid, granica);
    if(v1 != -1) return v1;
    else return znajdzsrodek(2 * w + 1, a, b, mid + 1, akt_b, granica);
}

struct trzy{
    int pref;
    int suff;
    int ind;
};

trzy szuk;

bool czy(int pref, int suff, int ile1, int ile2){
    int pocz = pref;
    int kon = n - suff + 1;
    a = pocz + 1;
    b = kon - 1;
    int v = iloscB(1, 1, base);
    if(ile1 > v) return false;
    a = 1;
    b = pocz;
    v = iloscB(1, 1, base);
    pref = ktaB(1, 1, base, 0, v + ile1 + 1) - 1;
    a = pocz + 1;
    b = kon - 1;
    v = iloscR(1, 1, base);
    if(ile2 > v) return false;
    return true;
}

int aktpref;
int aktsuff;

int ostatni(int w, int akt_a, int akt_b){
    if(akt_a == akt_b) {
        szuk.pref += drzew[w].sumanieakt;
        szuk.suff += drzew[w].sumaakt;
        return akt_a;
    }
    int mid = (akt_a + akt_b) / 2;
    if(czy(aktpref, aktsuff, szuk.pref + drzew[2 * w].sumanieakt, szuk.suff + drzew[2 * w].sumaakt)){
        szuk.pref += drzew[2 * w].sumanieakt;
        szuk.suff += drzew[2 * w].sumaakt;
        return ostatni(2 * w + 1, mid + 1, akt_b);
    }
    else{
        return ostatni(2 * w, akt_a, mid);
    }
}

int znajdzostatni(int w, int a, int b, int akt_a, int akt_b){
    if(a > b){
        szuk = {0, 0, b};
        return b;
    }
    if(a <= akt_a and akt_b <= b){
        if(czy(aktpref, aktsuff, szuk.pref + drzew[w].sumanieakt, szuk.suff + drzew[w].sumaakt) == true){
            szuk.pref += drzew[w].sumanieakt;
            szuk.suff += drzew[w].sumaakt;
            return -1;
        }
        else{
            int t = ostatni(w, akt_a, akt_b);
            szuk.ind = t;
            return t;
        }
    }
    if(akt_a > b or akt_b < a) return -1;
    int mid = (akt_a + akt_b) / 2;
    auto v1 = znajdzostatni(2 * w, a, b, akt_a, mid);
    if(v1 != -1) return v1;
    auto v2 = znajdzostatni(2 * w + 1, a, b, mid + 1, akt_b);
    return v2;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    M = n + 1;
    int l, r;
    cin >> s;
    int p1 = 0;
    int s1 = 0;
    for(int i = 0; i < n; ++i){
        if(s[i] == '>' or s[i] == 'R'){
            p1++;
        }
        else{
            break;
        }
    }
    for(int i = n - 1; i >= 0; --i){
        if(s[i] == '<' or s[i] == 'B'){
            s1++;
        }
        else{
            break;
        }
    }
    //liczenie drzewa strzalek
    {
    for(int i = 0; i < n; ++i){
        if(s[i] == '>' or s[i] == 'R'){
            strzalki[i + base] = {1, 0};
        }
        else{
            strzalki[i + base] = {0, 1};
        }
    }
    for(int i = base - 1; i > 0; --i){
        strzalki[i] = {strzalki[2 * i].sR + strzalki[2 * i + 1].sR, strzalki[2 * i].sB + strzalki[2 * i + 1].sB};
    }
    }

    //liczenie 2 czesci
    {
    krasnoludki.push_back(-1);
    for(int i = 0; i < m; ++i){
        cin >> l;
        krasnoludki.push_back(l);
        drugaczesc[i + base].swapy = {{0, l - 1, l + 1}, {l, n, l}};
    }
    for(int i = m + base; i < 2 * base; ++i){
        drugaczesc[i].swapy = {{0, n, 0}};
    }

    for(int i = base - 1; i > 0; --i){
        //cout << i << " i\n";
        auto v1 = drugaczesc[2 * i].swapy;
        auto v2 = drugaczesc[2 * i + 1].swapy;
        vector<c> odp;
        
        auto policz = [&](int a, int b, int dod){
            int p = 0;
            int k = v2.size() - 1;
            while(p != k){
                int sr = (p + k) / 2;
                if(v2[sr].b < a){
                    p = sr + 1;
                }
                else{
                    k = sr;
                }
            }
            if(v2[p].a <= a and b <= v2[p].b){
                //cout << (a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[p].dod << " if1\n";
                odp.push_back({(a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[p].dod});
                return;
            }
            //cout << a << " " << b << " ab\n";
            int curr = p;
            //cout << (a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " lewo\n";
            odp.push_back({(a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod});
            curr++;
            while(v2[curr].a <= b){
                if(v2[curr].b <= b){
                    //cout << (v2[curr].a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " mid\n";
                    odp.push_back({(v2[curr].a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod});
                }
                else{
                    //cout << (v2[curr].a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " prawo\n";
                    odp.push_back({(v2[curr].a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[curr].dod});
                    break;
                }
                if(curr == v2.size() - 1) break;
                curr++;
            }
            return;
        };

        for(auto u : v1){
            int valdod = (u.a + u.dod) % M;
            int valkon = (u.b + u.dod) % M;
            //cout << valdod << " " << valkon << " pk\n";
            if(valdod <= valkon){
                policz(valdod, valkon, u.dod);
            }
            else{
                policz(valdod, n, u.dod);
                policz(0, valkon, u.dod);
            }
        }
        vector<c> tmp;
        for(auto u : odp){
            if(u.a > u.b){
                tmp.push_back({0, u.b, u.dod});
                tmp.push_back({u.a, n, u.dod});
            }
            else{
                tmp.push_back(u);
            }
            tmp.back().dod %= M;
        }
        odp = tmp;
        // for(auto u : odp){
        //     cout << u.a << " " << u.b << " " << u.dod << " po zlozeniu\n";
        // }
        sort(odp.begin(),odp.end(),comp);
        drugaczesc[i].swapy = odp;
    }
    }
    
    for(int i = 1; i <= m; ++i){
        wylacz[krasnoludki[i]].push_back(i);
    }
    for(int i = base + m; i < 2 * base; ++i){
        drzew[i] = {0, 0, INF};
    }

    int q;
    cin >> q;
    for(int i = 0; i < q; ++i){
        cin >> l >> r;
        if(p1 + s1 == n){
            a = l;
            b = r;
            ans[i] = drugiwyn(1, 1, base, p1);
        }
        else{
            queries.push_back({p1, s1, i, l, r});
        }
    }
    cofnij();
    while(queries.size() > 0){
        sort(queries.begin(),queries.end(), comp2);
        // for(auto u : queries){
        //     cout << u.pref << " " << u.suff << " zapytanie\n";
        // }
        int it = 0;
        for(int i = 0; i <= n; ++i){
            if(it == queries.size()) break;
            for(auto u : wylacz[i]){
                //cout << u << " " << krasnoludki[u] << " wylaczyc\n";
                akt(u);
            }   
            while(it < queries.size() and queries[it].pref == i){
                auto u = queries[it];
                // for(int i = 1; i < 2 * base; ++i){
                //     cout << i << " " << drzew[i].minimalny << " mi\n";
                // }
                //cout << queries[it].a << " " << queries[it].b << " przedzial\n";
                int ktory = znajdzsrodek(1, u.a, u.b, 1, base, n - u.suff + 1);
                if(ktory == -1){
                    pair<int,int> tmp = {u.pref, u.suff};
                    if(krasnoludki[u.a] <= tmp.first){
                        tmp = dodajp(tmp.first, tmp.second, krasnoludki[u.a], n);
                    }
                    else{
                        tmp = dodajk(tmp.first, tmp.second, n - krasnoludki[u.a], n);
                    }
                    if(tmp.first + tmp.second == n){
                        a = u.a + 1;
                        b = u.b;
                        ans[u.org] = drugiwyn(1, 1, base, tmp.first);
                    }
                    else{
                        szuk = {0, 0, -1};
                        aktpref = u.pref;
                        aktsuff = u.suff;
                        znajdzostatni(1, u.a, u.b, 1, base);
                        if(szuk.ind == -1) szuk.ind = u.b;
                        trzy ile = szuk;
                        //cout << ile.ind << " il\n";
                        pair<int,int> p = {u.pref, u.suff};
                        if(ile.ind == u.b){
                            p = dodajp(p.first, p.second, ile.pref, n);
                            p = dodajk(p.first, p.second, ile.suff, n);
                            int kon = n - p.second + 1;
                            a = p.first + 1;
                            b = kon - 1;
                            ans[u.org] = p.first + iloscR(1, 1, base);
                        }
                        else{
                            p = dodajp(p.first, p.second, ile.pref, n);
                            p = dodajk(p.first, p.second, ile.suff, n);
                            ile.ind++;
                            if(krasnoludki[ile.ind] <= p.first){
                                p = dodajp(p.first, p.second, krasnoludki[ile.ind], n);
                            }
                            else{
                                p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n);
                            }
                            a = ile.ind + 1;
                            b = u.b;
                            ans[u.org] = drugiwyn(1, 1, base, p.first);
                        }
                    }
                }
                else{
                    if(ktory == u.a){
                        //cout << "#\n";
                        pair<int,int> p = {u.pref, u.suff};
                        p = dodajs(p.first, p.second, krasnoludki[u.a], n);
                        if(u.a == u.b){
                            int kon = n - p.second + 1;
                            a = p.first + 1;
                            b = kon - 1;
                            ans[u.org] = p.first + iloscR(1, 1, base);
                        }
                        else if(p.first + p.second == n){
                            a = u.a + 1;
                            b = u.b;
                            ans[u.org] = drugiwyn(1, 1, base, p.first);
                        }
                        else{
                            //cout << p.first << " " << p.second << " nowe\n";
                            nowe.push_back({p.first, p.second, u.org, u.a + 1, u.b});
                        }
                    }
                    else{
                        pair<int,int> tmp = {u.pref, u.suff};
                        if(krasnoludki[u.a] <= tmp.first){
                            tmp = dodajp(tmp.first, tmp.second, krasnoludki[u.a], n);
                        }
                        else{
                            tmp = dodajk(tmp.first, tmp.second, n - krasnoludki[u.a], n);
                        }
                        if(tmp.first + tmp.second == n){
                            a = u.a + 1;
                            b = u.b;
                            ans[u.org] = drugiwyn(1, 1, base, tmp.first);
                        }
                        else{
                            szuk = {0, 0, -1};
                            aktpref = u.pref;
                            aktsuff = u.suff;
                            znajdzostatni(1, u.a, ktory - 1, 1, base);
                            if(szuk.ind == -1) szuk.ind = ktory - 1;
                            trzy ile = szuk;
                            pair<int,int> p = {u.pref, u.suff};
                            //cout << ile.pref << " " << ile.suff << " " << ile.ind << " ile\n";
                            if(ile.ind != ktory - 1){
                                p = dodajp(p.first, p.second, ile.pref, n);
                                p = dodajk(p.first, p.second, ile.suff, n);
                                ile.ind++;
                                if(krasnoludki[ile.ind] <= p.first){
                                    p = dodajp(p.first, p.second, krasnoludki[ile.ind], n);
                                }
                                else{
                                    p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n);
                                }
                                a = ile.ind + 1;
                                b = u.b;
                                ans[u.org] = drugiwyn(1, 1, base, p.first);
                            }
                            else{
                                p = dodajp(p.first, p.second, ile.pref, n);
                                p = dodajk(p.first, p.second, ile.suff, n);
                                ile.ind++;
                                if(krasnoludki[ile.ind] <= p.first){
                                    p = dodajp(p.first, p.second, krasnoludki[ile.ind], n);
                                }
                                else if(krasnoludki[ile.ind] > n - p.second){
                                    p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n);
                                }
                                else{
                                    p = dodajs(p.first, p.second, krasnoludki[ile.ind], n);
                                }
                                //cout << p.first << " " << p.second << " nowa\n";
                                if(ile.ind == u.b){
                                    int kon = n - p.second + 1;
                                    a = p.first + 1;
                                    b = kon - 1;
                                    ans[u.org] = p.first + iloscR(1, 1, base);
                                }
                                else if(p.first + p.second == n){
                                    a = ile.ind + 1;
                                    b = u.b;
                                    ans[u.org] = drugiwyn(1, 1, base, p.first);
                                }
                                else{
                                    nowe.push_back({p.first, p.second, u.org, ile.ind + 1, u.b});
                                }
                            }
                        }   
                    }
                }
                ++it;
            }
        }
        queries = nowe;
        nowe.clear();
        cofnij();
    }
    for(int i = 0; i < q; ++i){
        cout << ans[i] << "\n";
    }
    return 0;
}

• 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