oj.uz

Submission #986374

# Submission time Handle Problem Language Result Execution time Memory
986374 2024-05-20T11:38:58 Z cig32 Modern Machine (JOI23_ho_t5) C++17
15 / 100
 3000 ms 4956 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
  char *stack, *send;
  stack = (char *)malloc(stsize);
  send = stack + stsize - 16;
  send = (char *)((uintptr_t)send / 16 * 16);
  asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r"(send));
  func();
  asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  free(stack);
} 
void solve(int tc) {
  int n, m, q;
  cin >> n >> m;
  char c[n+1]; // blue or red
  for(int i=1; i<=n; i++) cin >> c[i];
  int a[m+1];
  for(int i=1; i<=m; i++) cin >> a[i];
  cin >> q;
  int r[n+1], b[n+1];
  r[0] = b[0] = 0;
  for(int i=1; i<=n; i++) {
    r[i] = r[i-1] + (c[i] == 'R');
    b[i] = b[i-1] + (c[i] == 'B');
  }
  // q = 1
  while(q--) {
    int l, r;
    cin >> l >> r;
    char upd[n+1];
    for(int i=1; i<=n; i++) upd[i] = c[i];
    for(int i=l; i<=r; i++) {
      int pivot = a[i];
      int leftR = 0, rightB = 0;
      for(int j=1; j<=n; j++) {
        if(j < pivot) leftR += (upd[j] == 'R');
        if(j > pivot) rightB += (upd[j] == 'B');
      }
      if(rightB <= leftR) { // goes to the right
        int cnt = 0;
        for(int j=pivot-1; j>=1; j--) {
          cnt += (upd[j] == 'R');
          if(cnt == rightB) {
            for(int k=j; k<=n; k++) upd[k] = 'B';
            break;
          }
        }
        if(rightB == 0) {
          for(int j=pivot; j<=n; j++) upd[j] = 'B';
        }
      }
      else {
        int cnt = 0;
        for(int j=pivot+1; j<=n; j++) {
          cnt += (upd[j] == 'B');
          if(cnt == leftR + 1) {
            for(int k=j; k>=1; k--) upd[k] = 'R';
            break;
          }
        }
      }
      //for(int j=1; j<=n; j++) cout << upd[j];
      //cout << "\n";
    }
    int ans = 0;
    for(int i=1; i<=n; i++) ans += (upd[i] == 'R');
    cout << ans << "\n";
  }


}
void uwu() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
  #ifdef ONLINE_JUDGE
  uwu();
  #endif
  #ifndef ONLINE_JUDGE
  run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
  #endif
}
/*
g++ C.cpp -std=c++17 -O2 -o C
./C < input.txt

*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 35 ms 600 KB Output is correct
11 Correct 15 ms 604 KB Output is correct
12 Correct 34 ms 604 KB Output is correct
13 Correct 64 ms 604 KB Output is correct
14 Correct 52 ms 604 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 35 ms 600 KB Output is correct
11 Correct 15 ms 604 KB Output is correct
12 Correct 34 ms 604 KB Output is correct
13 Correct 64 ms 604 KB Output is correct
14 Correct 52 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3034 ms 4956 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 3071 ms 2908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 3071 ms 2908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 3071 ms 2908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 35 ms 600 KB Output is correct
11 Correct 15 ms 604 KB Output is correct
12 Correct 34 ms 604 KB Output is correct
13 Correct 64 ms 604 KB Output is correct
14 Correct 52 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3034 ms 4956 KB Time limit exceeded
19 Halted 0 ms 0 KB -