Submission #1182085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182085		Zbyszek99	Modern Machine (JOI23_ho_t5)	C++20	0 / 100	3095 ms	972 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;

int n,m;
string s;

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)
{
    //cerr << "\nnxt\n\n";
    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];
    }
    //cerr << R_cnt << " " << L_cnt << " " << cur_pref << " " << cur_suf << " " << v << " RL\n";
    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];
        }
    //    cerr << R2 << " " << R_cnt << " R2\n";
        if(R2 >= R_cnt)
        {
    //        cerr << ind_to_poz_R[ind[nxt_R[v]] + R_cnt] << " " << ind[nxt_R[v]] << " " << nxt_R[v] << " " << R_cnt << " ind\n";
            if(R_cnt != 0) return {cur_pref,n-ind_to_poz_R[ind[nxt_R[v]] + R_cnt]+1};
            return {min(cur_pref,v-1),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)];
        }
       // cerr << L2 << " L2\n";
        L_cnt++;
      //  cerr << L_cnt << " L_cnt\n";
        if(L2 >= L_cnt)
        {
      //      cerr << ind[prev_L[v]] << " ind\n";
            //if(L_cnt != 0) 
            if(L_cnt != 0) return {ind_to_poz_L[ind[prev_L[v]]+L_cnt],cur_suf};
            return {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;
        }
    }
   // rep2(i,1,n) cout << ind[i] << " ";
   // cout << " ind\n";
    int start_pref = 0;
    int start_suf = 0;
    rep2(i,1,n)
    {
   //     cout << arr[i] << " arr\n";
        if(arr[i] == 1) start_pref++;
        else break;
    }
    for(int i = n; i >= 1; i--)
    {
        if(arr[i] == -1) start_suf++;
        else break;
    }
   // cout << start_pref << " " << start_suf << " start\n";
    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];
    ind_to_poz_L[prefL[n]+1] = n;
    ind_to_poz_R[prefR[n]] = 0;
    int q;
    cin >> q;
    rep(i,q)
    {
        query_ans[i] = -1;
        int l,r;
        cin >> l >> r;
        int cur_pref = start_pref;
        int cur_suf = start_suf;
        rep2(j,l,r)
        {
            pii w = nxt_state(cur_pref,cur_suf,A[j]);
            cur_pref = w.ff;
            cur_suf = w.ss;
 //           cerr << cur_pref << " " << cur_suf << " cur_pref/suf\n";
        }
        cout << cur_pref + prefR[n-cur_suf] - prefR[cur_pref] << "\n"; 
    }
}

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