제출 #1188151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188151		niepamietamhasla	Modern Machine (JOI23_ho_t5)	C++20	62 / 100	3096 ms	67772 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;
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 drzew[2 * base];

int ans[MAXN];

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 drzew[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 drzew[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(drzew[2 * w].sB + curr < cel){
        return ktaB(2 * w + 1, mid + 1, akt_b, curr + drzew[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(drzew[2 * w + 1].sR + curr < cel){
        return ktaR(2 * w, akt_a, mid, curr + drzew[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};
        }
    }
}

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'){
            drzew[i + base] = {1, 0};
        }
        else{
            drzew[i + base] = {0, 1};
        }
    }
    for(int i = base - 1; i > 0; --i){
        drzew[i] = {drzew[2 * i].sR + drzew[2 * i + 1].sR, drzew[2 * i].sB + drzew[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){
        int a, b;
        cin >> a >> b;
        //cout << a << " " << b << " ab\n";
        int pref = p1;
        int suff = s1;
        bool czy = false;
        while(a <= b){
            //cerr << pref << " " << suff << " ps\n";
            if(pref + suff == n){
                cout << drugiwyn(1, a, b, 1, base, pref) << "\n";
                czy = true;
                break;
            }
            if(krasnoludki[a] <= pref){
                auto k = dodajp(pref, suff, krasnoludki[a], n);
                pref = k.first;
                suff = k.second;
            }
            else if(krasnoludki[a] > n - suff){
                //cout << "$\n";
                auto k = dodajk(pref, suff, n - krasnoludki[a], n);
                pref = k.first;
                suff = k.second;
            }
            else{
                //cout << "#\n";
                auto k = dodajs(pref, suff, krasnoludki[a], n);
                pref = k.first;
                suff = k.second;
            }
            a++;
        }
        //cout << pref << " " << suff << " ps\n";
        if(czy == true) continue;
        if(pref + suff == n){
            cout << pref << "\n";
        }
        else{
            int pocz = pref;
            int kon = n - suff + 1;
            cout << pref + iloscR(1, pocz + 1, kon - 1, 1, base) << "\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: 0 / 17
• Subtask 7: 0 / 21