fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Speed
  5. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6.  
  7. // Typedefs
  8. #define int long long
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12. #define all(x) (x).begin(), (x).end()
  13. #define rall(x) (x).rbegin(), (x).rend()
  14. #define sz(x) ((int)(x).size())
  15. #define endl '\n'
  16. #define yes cout << "yes\n"
  17. #define no cout << "no\n"
  18.  
  19. // Loops
  20. #define rep(i,a,b) for(int i=a;i<b;++i)
  21. #define per(i,a,b) for(int i=b-1;i>=a;--i)
  22. #define each(x, a) for (auto& x : a)
  23.  
  24. // Consts
  25. const int INF = 1e18;
  26. const int MOD = 1e9+7;
  27. const int N = 2e5 + 5;
  28.  
  29. // Math
  30. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  31. int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
  32.  
  33. int power(int a, int b, int m = MOD) {
  34.     int res = 1;
  35.     while (b > 0) {
  36.         if (b & 1) res = res * a % m;
  37.         a = a * a % m;
  38.         b >>= 1;
  39.     }
  40.     return res;
  41. }
  42.  
  43. int modinv(int a, int m = MOD) {
  44.     return power(a, m - 2, m);
  45. }
  46.  
  47. // Logic
  48. void solve() {
  49.     int n, q;
  50.     cin >> n >> q;
  51.     string s;
  52.     cin >> s;
  53.  
  54.     int base_val = 0;
  55.     int base_pairs = 0;
  56.  
  57.     int cnt_2b = 0;           // I ? H
  58.     int cnt_dedicated_L = 0;  // ... H
  59.     int cnt_dedicated_H = 0;  // I ...
  60.     int total_standard_cap = 0;
  61.  
  62.     int cnt_q = 0;
  63.  
  64.     auto is_H = [](char c) { return c == 'V' || c == 'X'; };
  65.     auto is_L = [](char c) { return c == 'I'; };
  66.     auto val_char = [](char c) {
  67.         if (c == 'X') return 10;
  68.         if (c == 'V') return 5;
  69.         if (c == 'I') return 1;
  70.         return 0;
  71.     };
  72.  
  73.     rep(i, 0, n) {
  74.         if (s[i] != '?') {
  75.             base_val += val_char(s[i]);
  76.         } else {
  77.             cnt_q++;
  78.         }
  79.     }
  80.  
  81.     rep(i, 0, n - 1) {
  82.         if (s[i] == 'I' && (s[i+1] == 'V' || s[i+1] == 'X')) {
  83.             base_pairs++;
  84.         }
  85.     }
  86.  
  87.     for (int i = 0; i < n; ) {
  88.         if (s[i] == '?') {
  89.             int j = i;
  90.             while (j < n && s[j] == '?') j++;
  91.             int len = j - i;
  92.  
  93.             char left = (i == 0) ? 'X' : s[i-1];
  94.             char right = (j == n) ? 'I' : s[j];
  95.  
  96.             bool left_is_L = is_L(left); 
  97.             bool right_is_H = is_H(right); 
  98.  
  99.             if (left_is_L && right_is_H) {
  100.                 if (len == 1) {
  101.                     cnt_2b++;
  102.                 } else {
  103.                     cnt_dedicated_L++;
  104.                     cnt_dedicated_H++;
  105.                     total_standard_cap += (len - 2) / 2;
  106.                 }
  107.             } else if (left_is_L && !right_is_H) {
  108.                 cnt_dedicated_H++;
  109.                 total_standard_cap += (len - 1) / 2;
  110.             } else if (!left_is_L && right_is_H) {
  111.                 cnt_dedicated_L++;
  112.                 total_standard_cap += (len - 1) / 2;
  113.             } else {
  114.                 total_standard_cap += len / 2;
  115.             }
  116.  
  117.             i = j;
  118.         } else {
  119.             i++;
  120.         }
  121.     }
  122.  
  123.     while(q--) {
  124.         int cX, cV, cI;
  125.         cin >> cX >> cV >> cI;
  126.  
  127.         int uI = min(cnt_q, cI);
  128.         int rem = cnt_q - uI;
  129.         int uV = min(rem, cV);
  130.         int uX = rem - uV;
  131.  
  132.         int N_L = uI;
  133.         int N_H = uV + uX;
  134.  
  135.         int current_pairs = base_pairs;
  136.  
  137.         int temp_2b = cnt_2b;
  138.  
  139.         int surplus_L = max(0LL, N_L - cnt_dedicated_L);
  140.         int take_L = min(temp_2b, surplus_L);
  141.         current_pairs += take_L;
  142.         N_L -= take_L;
  143.         temp_2b -= take_L;
  144.  
  145.         int surplus_H = max(0LL, N_H - cnt_dedicated_H);
  146.         int take_H = min(temp_2b, surplus_H);
  147.         current_pairs += take_H;
  148.         N_H -= take_H;
  149.         temp_2b -= take_H;
  150.  
  151.         if (temp_2b > 0) {
  152.             int fill_L = min(temp_2b, N_L);
  153.             current_pairs += fill_L;
  154.             N_L -= fill_L;
  155.             temp_2b -= fill_L;
  156.         }
  157.         if (temp_2b > 0) {
  158.             int fill_H = min(temp_2b, N_H);
  159.             current_pairs += fill_H;
  160.             N_H -= fill_H;
  161.             temp_2b -= fill_H;
  162.         }
  163.  
  164.         int use_L_ded = min(cnt_dedicated_L, N_L);
  165.         current_pairs += use_L_ded;
  166.         N_L -= use_L_ded;
  167.  
  168.         int use_H_ded = min(cnt_dedicated_H, N_H);
  169.         current_pairs += use_H_ded;
  170.         N_H -= use_H_ded;
  171.  
  172.         int use_std = min({N_L, N_H, total_standard_cap});
  173.         current_pairs += use_std;
  174.  
  175.         int ans = base_val + uX * 10 + uV * 5 + uI * 1 - 2 * current_pairs;
  176.         cout << ans << endl;
  177.     }
  178. }
  179.  
  180. // Main
  181. int32_t main() {
  182.     fast_io;
  183.  
  184.     int t;
  185.     cin >> t;
  186.     while (t--) {
  187.         solve();
  188.     }
  189.  
  190.     return 0;
  191. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
3 3
???
3 0 0
2 3 1
0 1 2
10 7
??IV?VXIV?
0 0 4
4 4 0
1 1 2
1 1 3
1 1 4
1 2 1
2 2 0
9 5
?V????IVV
9 2 4
4 1 5
0 1 4
4 8 1
3 2 7
3 2
I?V
0 1 0
0 0 1
stdout
copy 
30
9
5
25
43
36
27
25
42
53
19
17
19
33
17
9
5
https://ideone.com/hdUNdA
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!