Submission #731373

#	Time	Username	Problem	Language	Result	Execution time	Memory
731373		AdamGS	Modern Machine (JOI23_ho_t5)	C++17	25 / 100	3068 ms	3120 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=12e4+7;
char C[LIM];
int tr[4*LIM], lazy[4*LIM], T[LIM], N=1, n, m, q;
void spl(int v, int l, int r) {
  tr[2*v]=lazy[v]*(r-l+1)/2;
  tr[2*v+1]=lazy[v]*(r-l+1)/2;
  lazy[2*v]=lazy[2*v+1]=lazy[v];
  lazy[v]=-1;
}
void upd(int v, int l, int r, int a, int b, int x) {
  if(l>b || r<a) return;
  if(a<=l && r<=b) {
    tr[v]=(r-l+1)*x;
    lazy[v]=x;
    return;
  }
  if(lazy[v]!=-1) spl(v, l, r);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=tr[2*v]+tr[2*v+1];
}
int cnt(int v, int l, int r, int a, int b) {
  if(l>b || r<a) return 0;
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]!=-1) spl(v, l, r);
  int mid=(l+r)/2;
  return cnt(2*v, l, mid, a, b)+cnt(2*v+1, mid+1, r, a, b);
}
int znajdzb(int v, int l, int r, int k) {
  if(l==r) return l;
  if(lazy[v]!=-1) spl(v, l, r);
  int mid=(l+r)/2;
  int x=(mid-l+1)-tr[2*v];
  if(x>=k) return znajdzb(2*v, l, mid, k);
  return znajdzb(2*v+1, mid+1, r, k-x);
}
int znajdzr(int v, int l, int r, int k) {
  if(l==r) return l;
  if(lazy[v]!=-1) spl(v, l, r);
  int mid=(l+r)/2;
  int x=tr[2*v+1];
  if(x>=k) return znajdzr(2*v+1, mid+1, r, k);
  return znajdzr(2*v, l, mid, k-x);
}
void symuluj(int x) {
  int iler=cnt(1, 0, N-1, 0, x-1), ileb=n-x-1-cnt(1, 0, N-1, x+1, n-1), p=cnt(1, 0, N-1, x, x);
  if(iler<ileb) upd(1, 0, N-1, 0, znajdzb(1, 0, N-1, x+1+1-p), 1);
  else upd(1, 0, N-1, znajdzr(1, 0, N-1, n-x+p-1), n-1, 0);
}
void brutq() {
  while(N<n) N*=2;
  while(q--) {
    rep(i, 2*N) tr[i]=0;
    rep(i, n) if(C[i]=='R') tr[N+i]=1;
    for(int i=N-1; i; --i) tr[i]=tr[2*i]+tr[2*i+1];
    rep(i, 2*N) lazy[i]=-1;
    int l, r;
    cin >> l >> r; --l; --r;
    while(l<=r) {
      symuluj(T[l]);
      ++l;
    }
    cout << tr[1] << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  rep(i, n) cin >> C[i];
  rep(i, m) {
    cin >> T[i];
    --T[i];
  }
  cin >> q;
  if(q<=5) {
    brutq();
    return 0;
  }
  brutq();
}

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