Submission #1188703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188703		niepamietamhasla	Modern Machine (JOI23_ho_t5)	C++20	62 / 100	2582 ms	184608 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 > 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, 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, ll 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;
        //cout << pocz << " " << ile << " pi\n";
        pocz = (pocz - ile + 2 * M) % 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;

struct Node{
    ll suma;
    ll ile;
    Node *l, *r;

    Node(ll x, ll y) : ile(x), suma(y), l(nullptr), r(nullptr) {}
    Node(Node *ll, Node *rr) : ile(ll->ile + rr->ile), suma(ll->suma + rr->suma), l(ll), r(rr) {}
};


Node *roots[MAXN];

Node *build(int akt_a = 1, int akt_b = base){
    if(akt_a == akt_b) return new Node(0ll, 0ll);
    int mid = (akt_a + akt_b) / 2;
    return new Node(build(akt_a, mid), build(mid + 1, akt_b));
}

Node *add(Node *prev, ll val, int akt_a = 1, int akt_b = base){
    if(akt_a == akt_b) return new Node(prev->ile + 1, prev->suma + val);
    int mid = (akt_a + akt_b) / 2;
    if(val <= mid){
        return new Node(add(prev->l, val, akt_a, mid), prev->r);
    }
    else{
        return new Node(prev->l, add(prev->r, val, mid + 1, akt_b));
    }
}

pair<ll,ll> oblicz(Node *k, Node*p, int a, int b, int akt_a, int akt_b){
    if(a <= akt_a and akt_b <= b){
        return {k->ile - p->ile, k->suma - p->suma};
    }
    if(akt_a > b or akt_b < a) return {0ll, 0ll};
    int mid = (akt_a + akt_b) / 2;
    auto v1 = oblicz(k->l, p->l, a, b, akt_a, mid);
    auto v2 = oblicz(k->r, p->r, a, b, mid + 1, akt_b);
    return {v1.first + v2.first, v1.second + v2.second};
}

pair<ll,ll> obl(int k, int p, int a, int b){
    //cout << p << " " << k << " przedzial\n";
    //cout << a << " " << b << " wartosci\n";
    return oblicz(roots[k], roots[p-1], a, b, 1, base);
}

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

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



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;
    }
    }
    
    //liczenie trwalego drzewa ilosci elementu
    roots[0] = build();
    for(int i = 1; i <= m; ++i){
        roots[i] = add(roots[i - 1], krasnoludki[i]);
        //cout << roots[i]->ile << " " << roots[i]->suma << " " << i << " roots\n";
    }

    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;
            koniec[i] = -1;
        }
        for(int i = 1; i <= m; ++i){
            for(auto u : wlacz[i]){
                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(i - 1, queries[nr].a, 1, queries[nr].pref).second;
                auto t = obl(i - 1, queries[nr].a, n - queries[nr].suff + 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";
            for(auto u : wylacz[i]){
                //cout << koniec[u] << " koniec\n";
                if(isans[u] == 1) continue;
                //cout << u << " nr\n";
                //cout << "#\n";
                updejt[u][2] = -1;
                auto l = obl(i, queries[u].a, 1, queries[u].pref);
                //cout << l.first << " " << l.second << " l\n";
                updejt[u][0] = l.second;
                auto t = obl(i, queries[u].a, n - queries[u].suff + 1, base);
                updejt[u][1] = (n * t.first - t.second);
                curr.erase({queries[u].pref + 1, n - queries[u].suff, u});
                koniec[u] = queries[u].b;
            }
            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";
            pair<int,int> p = {queries[i].pref, queries[i].suff};
            //cout << p.first << " " << p.second << " ps\n";
            //cout << updejt[i][0] << " " << updejt[i][1] << " upd\n";
            if(czy(p.first, p.second, updejt[i][0], updejt[i][1], n) == false){
                //cout << "#\n";
                pair<int,int> tmp;
                if(krasnoludki[queries[i].a] <= p.first){
                    tmp = dodajp(p.first, p.second, krasnoludki[queries[i].a], n);
                }
                else{
                    tmp = dodajk(p.first, p.second, n - krasnoludki[queries[i].a], n);
                }
                if(tmp.first + tmp.second == n){
                    ans[queries[i].org] = drugiwyn(1, queries[i].a + 1, queries[i].b, 1, base, tmp.first);
                    continue;
                }
                int pocz = queries[i].a;
                int kon = koniec[i];
                while(pocz != kon){
                    int sr = (pocz + kon + 1) / 2;
                    auto pr = obl(sr, queries[i].a, 1, p.first);
                    auto su = obl(sr, queries[i].a, n - p.second + 1, base);
                    if(czy(p.first, p.second, pr.second, n * su.first - su.second, n)){
                        pocz = sr;
                    }
                    else{
                        kon = sr - 1;
                    }
                }
                auto pu = obl(pocz, queries[i].a, 1, p.first);
                auto su = obl(pocz, queries[i].a, n - p.second + 1, base);
                p = dodajp(p.first, p.second, pu.second, n);
                p = dodajk(p.first, p.second, n * su.first - su.second, n);
                if(krasnoludki[pocz + 1] <= p.first){
                    p = dodajp(p.first, p.second, krasnoludki[pocz + 1], n);
                }
                else{
                    p = dodajk(p.first, p.second, n - krasnoludki[pocz + 1], n);
                }
                ans[queries[i].org] = drugiwyn(1, pocz + 2, queries[i].b, 1, base, p.first);
                continue;
            }
            if(updejt[i][2] == -1){
                p = dodajp(p.first, p.second, updejt[i][0], n);
                //cout << p.first << " " << p.second << " po pocz\n";
                //cout << updejt[i][1] << " u1\n";
                p = dodajk(p.first, p.second, updejt[i][1], n);
                //cout << p.first << " " << p.second << " po obu\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{
                p = dodajp(p.first, p.second, updejt[i][0], n);
                //cout << p.first << " " << p.second << " po pocz\n";
                p = dodajk(p.first, p.second, updejt[i][1], n);
                //cout << p.first << " " << p.second << " po kon\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, n - updejt[i][2], n);
                }
                else{
                    p = dodajs(p.first, p.second, updejt[i][2], n);
                }
                //cout << p.first << " " << p.second << " po mid\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();
    }
    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: 0 / 17
• Subtask 7: 0 / 21