Submission #1182227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182227		Zbyszek99	Modern Machine (JOI23_ho_t5)	C++20	52 / 100	490 ms	91012 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct query
{
    int l,r,cur_pref,cur_suf,ind;
    bool operator<(const query& other) const
    {
        return cur_pref < other.cur_pref;
    }
};

int n,m;
string s;

struct seg
{
    int l,r,k;
    bool operator<(const seg& other) const
    {
        if(l != other.l) return l < other.l;
        return r < other.r;
    }
};

struct node
{
    vector<seg> segs;
    node()
    {
        segs.pb({0,n,0});
    }
    void def()
    {
        segs = {{0,n,0}};
    }
    void default_a(int a)
    {
        segs = {};
        if(a*2 < n)
        {
            segs.pb({0,a-1,a+1});
        }
        else
        {
            if(n - (a+1) >= 0) segs.pb({0,n-(a+1),a+1});
            segs.pb({n-(a+1)+1,a-1,0});
        }
        int s = (a+a) % (n+1);
        if(s + (n - a) <= n)
        {
            segs.pb({a,n,s});
        }
        else
        {
            segs.pb({a,a+n-s,s});
            segs.pb({a+n-s+1,n,0});
        }
        sort(all(segs));
    }
    node operator+(const node& other)
    {
        node res;
        res.segs = {};
        forall(it,segs)
        {
            seg w = {it.k,(int)1e9,-1};
            auto iter = lower_bound(other.segs.begin(),other.segs.end(), w);
            iter--;
            int cur = it.k;
            int cur_poz = it.l;
            int r = it.k + (it.r - it.l);
            while(cur <= r)
            {
                if((*iter).r >= r)
                {
                    res.segs.pb({cur_poz,it.r,(*iter).k + cur - (*iter).l});
                    break;
                }
                else
                {
                    int d = (*iter).r - cur;
                    res.segs.pb({cur_poz,cur_poz + d,(*iter).k + cur - (*iter).l});
                    cur = (*iter).r+1;
                    cur_poz += d+1;
                    iter++;
                }
            }
        }
        sort(all(res.segs));
        return res;
    }
    int get_val(int k)
    {
        auto it = lower_bound(segs.begin(),segs.end(),(seg){k,(int)1e9,-1});
        it--;
        return (*it).k + (k - (*it).l);
    }
};

const int tree_siz = 1024*256-1;
node drzewo[tree_siz];

int get_pref(int akt, int p1, int p2, int s1, int s2, int cur)
{
    if(p2 < s1 || p1 > s2) return cur;
    if(p1 >= s1 && p2 <= s2)
    {
        return drzewo[akt-1].get_val(cur);
    }
    cur = get_pref(akt*2,p1,(p1+p2)/2,s1,s2,cur);
    cur = get_pref(akt*2+1,(p1+p2)/2+1,p2,s1,s2,cur);
    return cur;
}

void build_tree(vi& a)
{
    m++;
    rep(i,m)
    {
        drzewo[tree_siz/2+i].default_a(a[i]);
    }
    rep2(i,tree_siz/2+m,tree_siz-1) drzewo[i].def();
    for(int i = tree_siz/2-1; i >= 0; i--)
    {
        drzewo[i] = drzewo[i*2+1] + drzewo[i*2+2];
    }
    m--;
}

int drzewoMin[tree_siz+1];

int find_first_less_rek(int akt, int l, int r, int w)
{
    if(l == r) return l;
    if(drzewoMin[akt*2] < w) return find_first_less_rek(akt*2,l,(l+r)/2,w);
    return find_first_less_rek(akt*2+1,(l+r)/2+1,r,w);
}

int find_first_less(int akt, int p1, int p2, int s1, int s2, int w)
{
    if(p2 < s1 || p1 > s2) return -1;
    if(p1 >= s1 && p2 <= s2)
    {
        if(drzewoMin[akt] < w)
        {
            return find_first_less_rek(akt,p1,p2,w);
        }
        return -1;
    }
    int w1 = find_first_less(akt*2,p1,(p1+p2)/2,s1,s2,w);
    if(w1 == -1)
    {
        return find_first_less(akt*2+1,(p1+p2)/2+1,p2,s1,s2,w);
    }
    return w1;
}

void updMin(int v)
{
    drzewoMin[v] = min(drzewoMin[v*2],drzewoMin[v*2+1]);
    if(v != 1) updMin(v/2);
}

void change(int ind, int w)
{
    drzewoMin[tree_siz/2+ind+1] = w;
    updMin((tree_siz/2+ind+1)/2);
}

pll drzewo_sum[tree_siz+1];

pll get_sum(int akt, int p1, int p2, int s1, int s2)
{
    if(s1 > s2) return {0,0};
    if(p2 < s1 || p1 > s2) return {0,0};
    if(p1 >= s1 && p2 <= s2) return drzewo_sum[akt];
    pll w1 = get_sum(akt*2,p1,(p1+p2)/2,s1,s2);
    pll w2 = get_sum(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
    return {w1.ff+w2.ff,w1.ss+w2.ss};
}

void upd_sum(int akt)
{
    drzewo_sum[akt].ff = drzewo_sum[akt*2].ff + drzewo_sum[akt*2+1].ff;
    drzewo_sum[akt].ss = drzewo_sum[akt*2].ss + drzewo_sum[akt*2+1].ss;   
    if(akt != 1) upd_sum(akt/2);
}

void change_sum(int ind, pii w)
{
    drzewo_sum[tree_siz/2+ind+1] = w;
    upd_sum((tree_siz/2+ind+1)/2);
}

int prev_L[120'002];
int nxt_R[120'002];
int prefL[120'002];
int prefR[120'002];
int ind[120'002];
int ind_to_poz_L[120'002];
int ind_to_poz_R[120'002];
int arr[120'002];
int query_ans[120'002];
int first_mid[120'002];
int nxt_pref[120'002];
int nxt_suf[120'002];
vi A;

pii nxt_state(int cur_pref, int cur_suf, int v)
{
    int R_cnt;
    int L_cnt;
    if(v <= cur_pref)
    {
        R_cnt = v-1;
        L_cnt = cur_suf + prefL[n-cur_suf] - prefL[cur_pref];
    }
    else if(v >= n-cur_suf+1)
    {
        R_cnt = cur_pref + prefR[n-cur_suf] - prefR[cur_pref];
        L_cnt = n-v;
    }
    else 
    {
        R_cnt = cur_pref + prefR[v-1] - prefR[cur_pref];
        L_cnt = cur_suf + prefL[n-cur_suf] - prefL[v];
    }
    if(R_cnt >= L_cnt)
    {
        swap(R_cnt,L_cnt);
        int R2 = 0;
        if(v > cur_pref)
        {
            R2 = prefR[min(n-cur_suf,v-1)] - prefR[cur_pref];
        }
        if(R2 >= R_cnt)
        {
            if(R_cnt != 0) return {cur_pref,n-ind_to_poz_R[ind[nxt_R[min(n-cur_suf+1,v)]] + R_cnt]+1};
            return {min(cur_pref,v-1),max(cur_suf,n-v+1)};
        }
        else
        {
            return {n-(n-(min(v-1,cur_pref) - (R_cnt-R2)+1)+1),n-(min(v-1,cur_pref) - (R_cnt-R2)+1)+1};
        }
    }
    else
    {
        swap(R_cnt,L_cnt);
        int L2 = 0;
        if(v <= n-cur_suf)
        {
            L2 = prefL[n-cur_suf]-prefL[max(cur_pref,v)];
        }
        L_cnt++;
        if(L2 >= L_cnt)
        {
            if(L_cnt != 0) return {ind_to_poz_L[ind[prev_L[max(v,cur_pref)]]+L_cnt],cur_suf};
            return {max(cur_pref,v),min(cur_suf,n-v)};
        }
        else
        {
            return {max(v+1,n-cur_suf+1)+(L_cnt-L2-1),n-(max(v+1,n-cur_suf+1)+(L_cnt-L2-1))};
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n >> m >> s;
    rep2(i,1,n)
    {
        arr[i] = 1;
        if(s[i-1] == 'B') arr[i] = -1;
    }
    int cnt = 1;
    prev_L[0] = 0;
    ind[0] = 0;
    rep2(i,1,n)
    {
        prev_L[i] = prev_L[i-1];
        if(arr[i] == -1)
        {
            prev_L[i] = i;
            ind[i] = cnt++;
            ind_to_poz_L[ind[i]] = i;
        }
    }
    cnt = 0;
    nxt_R[n+1] = n+1;
    ind[n+1] = -1;
    for(int i = n; i >= 1; i--)
    {
        nxt_R[i] = nxt_R[i+1];
        if(arr[i] == 1)
        {
            nxt_R[i] = i;
            ind[i] = cnt++;
            ind_to_poz_R[ind[i]] = i;
        }
    }
    int start_pref = 0;
    int start_suf = 0;
    rep2(i,1,n)
    {
        if(arr[i] == 1) start_pref++;
        else break;
    }
    for(int i = n; i >= 1; i--)
    {
        if(arr[i] == -1) start_suf++;
        else break;
    }
    rep2(i,1,n)
    {
        prefL[i] = prefL[i-1];
        prefR[i] = prefR[i-1];
        if(arr[i] == -1) prefL[i]++;
        else prefR[i]++;
    }
    A.resize(m+1,1);
    rep2(i,1,m) cin >> A[i];
    build_tree(A);
    ind_to_poz_L[prefL[n]+1] = n;
    ind_to_poz_R[prefR[n]] = 0;
    int q;
    cin >> q;
    vector<query> queries;
    rep(i,q)
    {
        query_ans[i] = -1;
        int l,r;
        cin >> l >> r;
        if(start_pref + start_suf == n)
        {
            query_ans[i] = get_pref(1,0,tree_siz/2,l,r,start_pref);
        }
        else
        {
            queries.pb({l,r,start_pref,start_suf,i});
        }
    }
    vector<query> new_queries;
    while(!queries.empty())
    {
        sort(all(queries));
        vector<pii> sort_pozy;
        rep2(i,1,m) sort_pozy.pb({A[i],i});
        rep2(i,1,m) change(i,A[i]);
        rep2(i,1,m) change_sum(i,{0,n-A[i]}); 
        sort(all(sort_pozy));
        int cur_p = 0;
        forall(it,queries)
        {
            int cur_pref = it.cur_pref;
            int cur_suf = it.cur_suf;
            while(cur_p < siz(sort_pozy) && sort_pozy[cur_p].ff <= cur_pref)
            {
                change(sort_pozy[cur_p].ss,1e9);
                change_sum(sort_pozy[cur_p].ss,{sort_pozy[cur_p].ff,0});
                cur_p++;
            }
            first_mid[it.ind] = find_first_less(1,0,tree_siz/2,it.l,it.r,n-cur_suf+1);
            if(first_mid[it.ind] == -1) first_mid[it.ind] = it.r+1;
            
            ll add = get_sum(1,0,tree_siz/2,it.l,first_mid[it.ind]-1).ff;
            nxt_pref[it.ind] = max(it.cur_pref,ind_to_poz_L[min((ll)prefL[n]+1,ind[prev_L[it.cur_pref]]+add)]);
            add = get_sum(1,0,tree_siz/2,it.l,first_mid[it.ind]-1).ss;
            if(ind[nxt_R[n-it.cur_suf+1]]+add != -1) nxt_suf[it.ind] = max(it.cur_suf,1+n-ind_to_poz_R[min((ll)prefR[n],ind[nxt_R[n-it.cur_suf+1]]+add)]);
            else nxt_suf[it.ind] = it.cur_suf;
            
            if(nxt_pref[it.ind] + nxt_suf[it.ind] >= n)
            {
                int l = it.l;
                int r = it.r;
                int p = -1;
                while(l <= r)
                {
                    int mid = (l+r)/2;
            
                    add = get_sum(1,0,tree_siz/2,it.l,mid).ff;
                    nxt_pref[it.ind] = max(it.cur_pref,ind_to_poz_L[min((ll)prefL[n]+1,ind[prev_L[it.cur_pref]]+add)]);
                    add = get_sum(1,0,tree_siz/2,it.l,mid).ss;
                    if(ind[nxt_R[n-it.cur_suf+1]]+add != -1) nxt_suf[it.ind] = max(it.cur_suf,1+n-ind_to_poz_R[min((ll)prefR[n],ind[nxt_R[n-it.cur_suf+1]]+add)]);
                    else nxt_suf[it.ind] = it.cur_suf;
                    
                    if(nxt_pref[it.ind] + nxt_suf[it.ind] < n)
                    {
                        p = mid;
                        l = mid+1;
                    }
                    else
                    {
                        r = mid-1;
                    }
                }
                p++;
                add = get_sum(1,0,tree_siz/2,it.l,p-1).ff;
                nxt_pref[it.ind] = max(it.cur_pref,ind_to_poz_L[min((ll)prefL[n]+1,ind[prev_L[it.cur_pref]]+add)]);
                add = get_sum(1,0,tree_siz/2,it.l,p-1).ss;
                if(ind[nxt_R[n-it.cur_suf+1]]+add != -1) nxt_suf[it.ind] = max(it.cur_suf,1+n-ind_to_poz_R[min((ll)prefR[n],ind[nxt_R[n-it.cur_suf+1]]+add)]);
                else nxt_suf[it.ind] = it.cur_suf;
                cur_pref = nxt_pref[it.ind];
                cur_suf = nxt_suf[it.ind];
                pii w = nxt_state(cur_pref,cur_suf,A[p]);
                cur_pref = w.ff;
                cur_suf = w.ss;
                if(p != it.r)
                {
                    query_ans[it.ind] = get_pref(1,0,tree_siz/2,p+1,it.r,cur_pref);
                }
                else
                {
                    query_ans[it.ind] = cur_pref;
                }
            }    
            else
            {
                cur_pref = nxt_pref[it.ind];
                cur_suf = nxt_suf[it.ind];
                if(first_mid[it.ind] <= it.r)
                {
                    pii w = nxt_state(cur_pref,cur_suf,A[first_mid[it.ind]]);
                    if(first_mid[it.ind] != it.r)
                    {
                        if(w.ff + w.ss != n)
                        {
                            new_queries.pb({first_mid[it.ind]+1,it.r,w.ff,w.ss,it.ind});
                        }
                        else
                        {
                            query_ans[it.ind] = get_pref(1,0,tree_siz/2,first_mid[it.ind]+1,it.r,w.ff);
                        }
                    }
                    else
                    {
                        query_ans[it.ind] = w.ff + prefR[n-w.ss] - prefR[w.ff];
                    }
                }
                else
                {
                    query_ans[it.ind] = cur_pref + prefR[n-cur_suf] - prefR[cur_pref];
                }
            }
        }
        queries = new_queries;
        new_queries = {};
    }
    rep(i,q) cout << query_ans[i] << "\n";
}

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