Submission #1188471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188471		niepamietamhasla	Modern Machine (JOI23_ho_t5)	C++20	40 / 100	668 ms	77752 KiB

Main

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


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 drugiwyn(int w, int a, int b, int akt_a, int akt_b, int 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, a, b, akt_a, mid, curr);
    curr = drugiwyn(2 * w + 1, a, b, mid + 1, akt_b, curr);
    return curr;
}

struct e{
    int sR;
    int sB;
};

e strzalki[2 * base];

int iloscR(int w, int a, int b, 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, a, b, akt_a, mid) + iloscR(2 * w + 1, a, b, mid + 1, akt_b);
}

int iloscB(int w, int a, int b, 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, a, b, akt_a, mid) + iloscB(2 * w + 1, a, b, 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;
    int v = iloscB(1, pocz + 1, kon - 1, 1, base);
    if(ile >= v){
        pocz = kon - 1;
        ile -= v;
        pocz = (pocz + ile) % M;
        kon = pocz + 1;
        return {pocz, n - pocz};
    }
    v = iloscB(1, 1, pocz, 1, base);
    return {ktaB(1, 1, base, 0, v + ile + 1) - 1, suff};
}

pair<int,int> dodajk(int pref, int suff, int ile, int n){
    int pocz = pref;
    int kon = n - suff + 1;
    int v = iloscR(1, pocz + 1, kon - 1, 1, base);
    //cout << pocz << " " << kon << " pk\n";
    //cout << ile << " " << v << " il\n";
    if(ile >= v){
        //cout << suff << " " << ile + 1 << " si\n";
        ile -= v;
        pocz = (pocz - ile + M * 2) % M;
        return {pocz, n - pocz};
    }
    v = iloscR(1, kon, base, 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;
    int iR2 = iloscR(1, pocz + 1, mid - 1, 1, base);
    int iB1 = suff;
    int iB2 = iloscB(1, mid + 1, kon - 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{
            int v = iloscR(1, mid, base, 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{
            int v = iloscB(1, 1, mid, 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;



pair<int,int> drzew[2 * base];
void dodaj(int val){
    int w = val + base - 1;
    drzew[w].first++;
    drzew[w].second += val;
    w /= 2;
    while(w != 0){
        drzew[w].first = drzew[2 * w].first + drzew[2 * w + 1].first;
        drzew[w].second = drzew[2 * w].second + drzew[2 * w + 1].second;
        w /= 2;
    }
    return;
}

pair<int,int> obl(int w, int a, int b, int akt_a, int akt_b){
    if(a <= akt_a and akt_b <= b){
        return drzew[w];
    }
    if(akt_a > b or akt_b < a) return {0, 0};
    int mid = (akt_a + akt_b) / 2;
    auto v1 = obl(2 * w, a, b, akt_a, mid);
    auto v2 = obl(2 * w + 1, a, b, mid + 1, akt_b);
    return {v1.first + v2.first, v1.second + v2.second};
}

void czysc(){
    for(int i = 1; i < 2 * base; ++i){
        drzew[i] = {0, 0};
    }
    return;
}

int isans[MAXN];
vector<int> wlacz[MAXN];
vector<int> wylacz[MAXN];
array<int, 3> updejt[MAXN];
set<array<int, 3>> curr;
int koniec[MAXN];

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    cin >> n >> m;
    M = n + 1;
    int a, b;
    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 >> a;
        krasnoludki.push_back(a);
        drugaczesc[i + base].swapy = {{0, a - 1, a + 1}, {a, n, a}};
    }
    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;
    }
    }
    
    int q;
    cin >> q;
    for(int i = 0; i < q; ++i){
        cin >> a >> b;
        if(p1 + s1 == n){
            ans[i] = drugiwyn(1, a, b, 1, base, p1);
        }
        else{
            queries.push_back({p1, s1, i, a, b});
        }
    }

    while(queries.size() > 0){
        //cout << queries.size() << " sajz\n";
        for(int i = 0; i < queries.size(); ++i){
            //cout << queries[i].a << " " << queries[i].b << " ab\n";
            wlacz[queries[i].a].push_back(i);
            wylacz[queries[i].b].push_back(i);
            isans[i] = 0;
            updejt[i][2] = -1;
            updejt[i][0] = 0;
            updejt[i][1] = 0;
            koniec[i] = -1;
        }
        for(int i = 1; i <= m; ++i){
            for(auto u : wlacz[i]){
                //cout << u << " " << i << " wl\n";
                updejt[u][0] = -obl(1, 1, queries[u].pref, 1, base).second;
                auto t = obl(1, n - queries[u].suff + 1, base, 1, base);
                updejt[u][1] = -(n * t.first - t.second);
                //cout << queries[u].pref + 1 << " " << n - queries[u].suff << " srodek\n";
                curr.insert({queries[u].pref + 1, n - queries[u].suff, u});
            }
            wlacz[i].clear();
            while(curr.size() > 0){
                //cout << (*curr.begin())[0] << " " << (*curr.begin())[1] << " pierw\n";
                auto it = curr.upper_bound({krasnoludki[i] + 1, 0, 0});
                if(it == curr.begin()) break;
                --it;
                if((*it)[0] > krasnoludki[i] or (*it)[1] < krasnoludki[i]) break;
                //cout << "wej\n";
                int nr = (*it)[2];
                isans[nr] = 1;
                updejt[nr][2] = krasnoludki[i];
                updejt[nr][0] += obl(1, 1, queries[nr].pref, 1, base).second;
                auto t = obl(1, n - queries[nr].suff + 1, base, 1, base);
                updejt[nr][1] += (n * t.first - t.second);
                //cout << i << " i\n"; 
                koniec[nr] = i;
                //cout << nr << " ustaw koniec\n";
                curr.erase(it);
            }
            //cout << krasnoludki[i] << " dod\n";
            dodaj(krasnoludki[i]);
            for(auto u : wylacz[i]){
                //cout << u << " nr\n";
                //cout << koniec[u] << " koniec\n";
                if(isans[u] == 1) continue;
                //cout << "#\n";
                updejt[u][2] = -1;
                updejt[u][0] += obl(1, 1, queries[u].pref, 1, base).second;
                auto t = obl(1, n - queries[u].suff + 1, base, 1, base);
                updejt[u][1] += (n * t.first - t.second);
                curr.erase({queries[u].pref + 1, n - queries[u].suff, u});
            }
            wylacz[i].clear();
        }
        curr.clear();
        //cout << "po\n";
        for(int i = 0; i < queries.size(); ++i){
            //cout << updejt[i][0] << " " << updejt[i][1] << " " << updejt[i][2] << " update\n";
            if(updejt[i][2] == -1){
                pair<int,int> p = {queries[i].pref, queries[i].suff};
                p = dodajp(p.first, p.second, updejt[i][0], n);
                p = dodajk(p.first, p.second, updejt[i][1], n);
                if(p.first + p.second == n){
                    ans[queries[i].org] = p.first;
                }
                else{
                    int pocz = p.first;
                    int kon = n - p.second + 1;
                    ans[queries[i].org] = p.first + iloscR(1, pocz + 1, kon - 1, 1, base);
                }
            }
            else{
                pair<int,int> p = {queries[i].pref, queries[i].suff};
                p = dodajp(p.first, p.second, updejt[i][0], n);
                p = dodajk(p.first, p.second, updejt[i][1], n);
                if(updejt[i][2] <= p.first){
                    p = dodajp(p.first, p.second, updejt[i][2], n);
                }
                else if(updejt[i][2] > n - p.second){
                    p = dodajk(p.first, p.second, updejt[i][2], n);
                }
                else{
                    p = dodajs(p.first, p.second, updejt[i][2], n);
                }

                if(koniec[i] == queries[i].b){
                    if(p.first + p.second == n){
                        ans[queries[i].org] = p.first;
                    }
                    else{
                        int pocz = p.first;
                        int kon = n - p.second + 1;
                        ans[queries[i].org] = p.first + iloscR(1, pocz + 1, kon - 1, 1, base);
                    }
                }
                else if(p.first + p.second == n){
                    ans[queries[i].org] = drugiwyn(1, koniec[i] + 1, queries[i].b, 1, base, p.first);
                }
                else{
                    //cout << p.first << " " << p.second << " po srodku\n";
                    nowe.push_back({p.first, p.second, queries[i].org, koniec[i] + 1, queries[i].b});
                }
            }
        }
        queries = nowe;
        nowe.clear();
        czysc();
    }
    for(int i = 0; i < q; ++i){
        cout << ans[i] << " ";
    }
    cout << "\n";
    return 0;
}

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