oj.uz

Submission #1018117

# Submission time Handle Problem Language Result Execution time Memory
1018117 2024-07-09T14:40:33 Z bachhoangxuan Modern Machine (JOI23_ho_t5) C++17
100 / 100
 805 ms 243836 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mpp make_pair
#define fi first
#define se second
const int maxn = 120005;
const int LOG = 18;

int f(int x){
    return (x?32-__builtin_clz(x):0);
}
int n,m,q,a[maxn];
char s[maxn];

vector<pii> T[4*maxn];
void build(int l,int r,int id){
    if(l==r){
        int x=a[l];
        if(x==n) T[id]={{n-1,0},{n,-1}};
        else if(n-x-1<x-1) T[id]={{n-x-1,x+1},{x-1,x-n},{n,x-n-1}};
        else T[id]={{x-1,x+1},{n-x,x},{n,x-n-1}};
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    int lt=0;
    for(auto [rt,val]:T[id<<1]){
        int pl=lower_bound(T[id<<1|1].begin(),T[id<<1|1].end(),mpp(lt+val,INT_MIN))-T[id<<1|1].begin();
        int pr=lower_bound(T[id<<1|1].begin(),T[id<<1|1].end(),mpp(rt+val,INT_MIN))-T[id<<1|1].begin();
        for(int i=pl;i<=pr;i++){
            auto [lst,nval]=T[id<<1|1][i];
            int pos=min(lst-val,rt);
            T[id].push_back({pos,val+nval});
        }
        lt=rt+1;
    }
}
int query(int l,int r,int id,int tl,int tr,int t){
    if(tr<l || r<tl) return t;
    if(tl<=l && r<=tr){
        auto it=lower_bound(T[id].begin(),T[id].end(),mpp(t,INT_MIN));
        return t+it->se;
    }
    int mid=(l+r)>>1;
    return query(mid+1,r,id<<1|1,tl,tr,query(l,mid,id<<1,tl,tr,t));
}



int nxt[LOG][LOG][maxn],cnt[maxn];
ll ca[LOG][maxn],cb[LOG][maxn];
int pa[maxn],sa,pb[maxn],sb;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=1;i<=m;i++) cin >> a[i];
    for(int i=1;i<=n+1;i++) if(s[i]!='R') pa[++sa]=i-1;
    for(int i=n;i>=0;i--) if(s[i]!='B') pb[++sb]=n-i;
    for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(s[i]=='B');
    for(int x=0;x<LOG;x++){
        int X=(x?(1<<(x-1)):0);
        for(int y=0;y<LOG;y++){
            int Y=(y?(1<<(y-1)):0);
            nxt[x][y][m+1]=m+1;
            for(int i=m;i>=1;i--) nxt[x][y][i]=(X<a[i] && a[i]<=n-Y)?i:nxt[x][y][i+1];
        }
        for(int i=1;i<=m;i++){
            ca[x][i]=(a[i]<=X?a[i]:0)+ca[x][i-1];
            cb[x][i]=(a[i]>n-X?n-a[i]:0)+cb[x][i-1];
        }
    }
    build(1,m,1);
    cin >> q;
    for(int i=1;i<=q;i++){
        int l,r;cin >> l >> r;
        int ta=1,tb=1,t=-1;
        while(true){
            auto g = [&](int x){
                if(x<=pa[ta]) return 0;
                else if(x>n-pb[tb]) return 1;
                else return (int)(s[x]=='B');
            };
            int xa=f(pa[ta]),xb=f(pb[tb]);
            int i=min(nxt[xa][xb][l],r+1);
            int da=min(ca[xa][i-1]-ca[xa][l-1],1LL*n);
            int db=min(cb[xb][i-1]-cb[xb][l-1],1LL*n);
            //cout << i << ' ' << da << ' ' << db << ' ' << pa[ta] << ' ' << pb[tb] << '\n';
            if(pa[min(sa,ta+da)]+pb[min(sb,tb+db)]<n){
                ta+=da,tb+=db;
                if(i==r+1) break;
                int bc=cnt[n-pb[tb]]-cnt[pa[ta]]+pb[tb],x=a[i]+g(a[i]);
                //cout << x << ' ' << bc << '\n';
                if(x<=bc){
                    if(x>=bc-pb[tb]){t=n-bc+x,l=i+1;break;}
                    else ta+=x;
                }
                else{
                    x=n-a[i]+(g(a[i])^1);
                    if(x>=n-bc-pa[ta]){
                        t=n-bc-x,l=i+1;
                        break;
                    }
                    else tb+=x;
                }
            }
            else{
                int lt=l,rt=i-1;
                while(lt<rt){
                    int mid=(lt+rt)>>1;
                    int da=min(ca[xa][mid]-ca[xa][l-1],1LL*n);
                    int db=min(cb[xb][mid]-cb[xb][l-1],1LL*n);
                    if(pa[min(sa,ta+da)]+pb[min(sb,tb+db)]<n) lt=mid+1;
                    else rt=mid;
                }
                int da=min(ca[xa][lt-1]-ca[xa][l-1],1LL*n);
                int db=min(cb[xb][lt-1]-cb[xb][l-1],1LL*n);
                ta+=da;tb+=db;l=lt+1;
                int bc=cnt[n-pb[tb]]-cnt[pa[ta]]+pb[tb],x=a[lt]+g(a[lt]);
                if(x<=bc) t=n-bc+x;
                else t=n-bc-(n-a[lt]+(g(a[lt])^1));
                break;
            }
            l=i+1;
        }
        //cout << t << ' ' << pb[tb] << ' ' << pa[ta] << '\n';
        if(t==-1) cout << n-pb[tb]-(cnt[n-pb[tb]]-cnt[pa[ta]]) << '\n';
        else cout << ((l<=r)?query(1,m,1,l,r,t):t) << '\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30812 KB Output is correct
2 Correct 5 ms 28764 KB Output is correct
3 Correct 4 ms 30812 KB Output is correct
4 Correct 4 ms 28764 KB Output is correct
5 Correct 6 ms 30812 KB Output is correct
6 Correct 5 ms 28764 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 4 ms 28764 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30812 KB Output is correct
2 Correct 5 ms 28764 KB Output is correct
3 Correct 4 ms 30812 KB Output is correct
4 Correct 4 ms 28764 KB Output is correct
5 Correct 6 ms 30812 KB Output is correct
6 Correct 5 ms 28764 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 4 ms 28764 KB Output is correct
10 Correct 16 ms 41820 KB Output is correct
11 Correct 25 ms 40540 KB Output is correct
12 Correct 24 ms 40796 KB Output is correct
13 Correct 17 ms 39260 KB Output is correct
14 Correct 15 ms 40416 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30812 KB Output is correct
2 Correct 5 ms 28764 KB Output is correct
3 Correct 4 ms 30812 KB Output is correct
4 Correct 4 ms 28764 KB Output is correct
5 Correct 6 ms 30812 KB Output is correct
6 Correct 5 ms 28764 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 4 ms 28764 KB Output is correct
10 Correct 16 ms 41820 KB Output is correct
11 Correct 25 ms 40540 KB Output is correct
12 Correct 24 ms 40796 KB Output is correct
13 Correct 17 ms 39260 KB Output is correct
14 Correct 15 ms 40416 KB Output is correct
15 Correct 5 ms 30812 KB Output is correct
16 Correct 4 ms 28764 KB Output is correct
17 Correct 5 ms 28764 KB Output is correct
18 Correct 309 ms 218496 KB Output is correct
19 Correct 348 ms 228424 KB Output is correct
20 Correct 352 ms 240580 KB Output is correct
21 Correct 321 ms 240836 KB Output is correct
22 Correct 385 ms 234732 KB Output is correct
23 Correct 197 ms 231380 KB Output is correct
24 Correct 194 ms 233868 KB Output is correct
25 Correct 189 ms 233928 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30808 KB Output is correct
2 Correct 250 ms 212584 KB Output is correct
3 Correct 276 ms 212560 KB Output is correct
4 Correct 171 ms 206160 KB Output is correct
5 Correct 192 ms 212560 KB Output is correct
6 Correct 188 ms 212564 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30808 KB Output is correct
2 Correct 250 ms 212584 KB Output is correct
3 Correct 276 ms 212560 KB Output is correct
4 Correct 171 ms 206160 KB Output is correct
5 Correct 192 ms 212560 KB Output is correct
6 Correct 188 ms 212564 KB Output is correct
7 Correct 5 ms 36700 KB Output is correct
8 Correct 6 ms 36700 KB Output is correct
9 Correct 6 ms 37164 KB Output is correct
10 Correct 12 ms 46940 KB Output is correct
11 Correct 586 ms 241824 KB Output is correct
12 Correct 658 ms 241352 KB Output is correct
13 Correct 387 ms 241348 KB Output is correct
14 Correct 431 ms 241348 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30808 KB Output is correct
2 Correct 250 ms 212584 KB Output is correct
3 Correct 276 ms 212560 KB Output is correct
4 Correct 171 ms 206160 KB Output is correct
5 Correct 192 ms 212560 KB Output is correct
6 Correct 188 ms 212564 KB Output is correct
7 Correct 5 ms 36700 KB Output is correct
8 Correct 5 ms 36800 KB Output is correct
9 Correct 5 ms 36880 KB Output is correct
10 Correct 6 ms 36700 KB Output is correct
11 Correct 5 ms 36700 KB Output is correct
12 Correct 5 ms 36700 KB Output is correct
13 Correct 5 ms 36928 KB Output is correct
14 Correct 6 ms 38744 KB Output is correct
15 Correct 5 ms 36700 KB Output is correct
16 Correct 5 ms 38748 KB Output is correct
17 Correct 17 ms 47452 KB Output is correct
18 Correct 308 ms 218472 KB Output is correct
19 Correct 412 ms 220364 KB Output is correct
20 Correct 532 ms 222924 KB Output is correct
21 Correct 561 ms 226504 KB Output is correct
22 Correct 639 ms 229640 KB Output is correct
23 Correct 616 ms 229912 KB Output is correct
24 Correct 314 ms 218592 KB Output is correct
25 Correct 342 ms 218400 KB Output is correct
26 Correct 156 ms 209988 KB Output is correct
27 Correct 159 ms 210040 KB Output is correct
28 Correct 341 ms 235460 KB Output is correct
29 Correct 315 ms 230704 KB Output is correct

Subtask #7
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30812 KB Output is correct
2 Correct 5 ms 28764 KB Output is correct
3 Correct 4 ms 30812 KB Output is correct
4 Correct 4 ms 28764 KB Output is correct
5 Correct 6 ms 30812 KB Output is correct
6 Correct 5 ms 28764 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 4 ms 28764 KB Output is correct
10 Correct 16 ms 41820 KB Output is correct
11 Correct 25 ms 40540 KB Output is correct
12 Correct 24 ms 40796 KB Output is correct
13 Correct 17 ms 39260 KB Output is correct
14 Correct 15 ms 40416 KB Output is correct
15 Correct 5 ms 30812 KB Output is correct
16 Correct 4 ms 28764 KB Output is correct
17 Correct 5 ms 28764 KB Output is correct
18 Correct 309 ms 218496 KB Output is correct
19 Correct 348 ms 228424 KB Output is correct
20 Correct 352 ms 240580 KB Output is correct
21 Correct 321 ms 240836 KB Output is correct
22 Correct 385 ms 234732 KB Output is correct
23 Correct 197 ms 231380 KB Output is correct
24 Correct 194 ms 233868 KB Output is correct
25 Correct 189 ms 233928 KB Output is correct
26 Correct 5 ms 30808 KB Output is correct
27 Correct 250 ms 212584 KB Output is correct
28 Correct 276 ms 212560 KB Output is correct
29 Correct 171 ms 206160 KB Output is correct
30 Correct 192 ms 212560 KB Output is correct
31 Correct 188 ms 212564 KB Output is correct
32 Correct 5 ms 36700 KB Output is correct
33 Correct 6 ms 36700 KB Output is correct
34 Correct 6 ms 37164 KB Output is correct
35 Correct 12 ms 46940 KB Output is correct
36 Correct 586 ms 241824 KB Output is correct
37 Correct 658 ms 241352 KB Output is correct
38 Correct 387 ms 241348 KB Output is correct
39 Correct 431 ms 241348 KB Output is correct
40 Correct 5 ms 36700 KB Output is correct
41 Correct 5 ms 36800 KB Output is correct
42 Correct 5 ms 36880 KB Output is correct
43 Correct 6 ms 36700 KB Output is correct
44 Correct 5 ms 36700 KB Output is correct
45 Correct 5 ms 36700 KB Output is correct
46 Correct 5 ms 36928 KB Output is correct
47 Correct 6 ms 38744 KB Output is correct
48 Correct 5 ms 36700 KB Output is correct
49 Correct 5 ms 38748 KB Output is correct
50 Correct 17 ms 47452 KB Output is correct
51 Correct 308 ms 218472 KB Output is correct
52 Correct 412 ms 220364 KB Output is correct
53 Correct 532 ms 222924 KB Output is correct
54 Correct 561 ms 226504 KB Output is correct
55 Correct 639 ms 229640 KB Output is correct
56 Correct 616 ms 229912 KB Output is correct
57 Correct 314 ms 218592 KB Output is correct
58 Correct 342 ms 218400 KB Output is correct
59 Correct 156 ms 209988 KB Output is correct
60 Correct 159 ms 210040 KB Output is correct
61 Correct 341 ms 235460 KB Output is correct
62 Correct 315 ms 230704 KB Output is correct
63 Correct 587 ms 233420 KB Output is correct
64 Correct 805 ms 243484 KB Output is correct
65 Correct 692 ms 243836 KB Output is correct
66 Correct 746 ms 237252 KB Output is correct
67 Correct 222 ms 209868 KB Output is correct
68 Correct 206 ms 209744 KB Output is correct
69 Correct 207 ms 209232 KB Output is correct
70 Correct 210 ms 209232 KB Output is correct
71 Correct 473 ms 233812 KB Output is correct
72 Correct 440 ms 234192 KB Output is correct
73 Correct 440 ms 234192 KB Output is correct
74 Correct 752 ms 242120 KB Output is correct
75 Correct 334 ms 236228 KB Output is correct
76 Correct 370 ms 236484 KB Output is correct