fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  5.  
  6. #define int long long
  7. #define pb push_back
  8. #define ff first
  9. #define ss second
  10. #define all(x) (x).begin(), (x).end()
  11. #define rall(x) (x).rbegin(), (x).rend()
  12. #define sz(x) ((int)(x).size())
  13. #define endl '\n'
  14. #define yes cout << "yes\n"
  15. #define no cout << "no\n"
  16.  
  17. #define rep(i,a,b) for(int i=a;i<b;++i)
  18. #define per(i,a,b) for(int i=b-1;i>=a;--i)
  19. #define each(x, a) for (auto& x : a)
  20.  
  21. const int INF = 1e18;
  22. const int MOD = 1e9+7;
  23. const int N = 2e5 + 5;
  24.  
  25. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  26. int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
  27.  
  28. int power(int a, int b, int m = MOD) {
  29.     int res = 1;
  30.     while (b > 0) {
  31.         if (b & 1) res = res * a % m;
  32.         a = a * a % m;
  33.         b >>= 1;
  34.     }
  35.     return res;
  36. }
  37.  
  38. int modinv(int a, int m = MOD) {
  39.     return power(a, m - 2, m);
  40. }
  41.  
  42. void solve() {
  43.     int n, q;
  44.     cin >> n >> q;
  45.     string s;
  46.     cin >> s;
  47.  
  48.     int bv = 0;
  49.     int bp = 0;
  50.  
  51.     int c2 = 0; 
  52.     int cl = 0; 
  53.     int ch = 0; 
  54.     int ts = 0; 
  55.  
  56.     int cq = 0;
  57.  
  58.     auto ish = [](char c) { return c == 'V' || c == 'X'; };
  59.     auto isl = [](char c) { return c == 'I'; };
  60.     auto vc = [](char c) {
  61.         if (c == 'X') return 10;
  62.         if (c == 'V') return 5;
  63.         if (c == 'I') return 1;
  64.         return 0;
  65.     };
  66.  
  67.     rep(i, 0, n) {
  68.         if (s[i] != '?') {
  69.             bv += vc(s[i]);
  70.         } else {
  71.             cq++;
  72.         }
  73.     }
  74.  
  75.     rep(i, 0, n - 1) {
  76.         if (s[i] == 'I' && (s[i+1] == 'V' || s[i+1] == 'X')) {
  77.             bp++;
  78.         }
  79.     }
  80.  
  81.     for (int i = 0; i < n; ) {
  82.         if (s[i] == '?') {
  83.             int j = i;
  84.             while (j < n && s[j] == '?') j++;
  85.             int len = j - i;
  86.  
  87.             char l = (i == 0) ? 'X' : s[i-1];
  88.             char r = (j == n) ? 'I' : s[j];
  89.  
  90.             bool ll = isl(l); 
  91.             bool rh = ish(r); 
  92.  
  93.             if (ll && rh) {
  94.                 if (len == 1) {
  95.                     c2++;
  96.                 } else {
  97.                     cl++;
  98.                     ch++;
  99.                     ts += (len - 2) / 2;
  100.                 }
  101.             } else if (ll && !rh) {
  102.                 ch++;
  103.                 ts += (len - 1) / 2;
  104.             } else if (!ll && rh) {
  105.                 cl++;
  106.                 ts += (len - 1) / 2;
  107.             } else {
  108.                 ts += len / 2;
  109.             }
  110.  
  111.             i = j;
  112.         } else {
  113.             i++;
  114.         }
  115.     }
  116.  
  117.     while(q--) {
  118.         int cx, cv, ci;
  119.         cin >> cx >> cv >> ci;
  120.  
  121.         int ui = min(cq, ci);
  122.         int rem = cq - ui;
  123.         int uv = min(rem, cv);
  124.         int ux = rem - uv;
  125.  
  126.         int nl = ui;
  127.         int nh = uv + ux;
  128.  
  129.         int cp = bp;
  130.  
  131.         int t2 = c2;
  132.  
  133.         int sl = max(0LL, nl - cl);
  134.         int tl = min(t2, sl);
  135.         cp += tl;
  136.         nl -= tl;
  137.         t2 -= tl;
  138.  
  139.         int sh = max(0LL, nh - ch);
  140.         int th = min(t2, sh);
  141.         cp += th;
  142.         nh -= th;
  143.         t2 -= th;
  144.  
  145.         if (t2 > 0) {
  146.             int fl = min(t2, nl);
  147.             cp += fl;
  148.             nl -= fl;
  149.             t2 -= fl;
  150.         }
  151.         if (t2 > 0) {
  152.             int fh = min(t2, nh);
  153.             cp += fh;
  154.             nh -= fh;
  155.             t2 -= fh;
  156.         }
  157.  
  158.         int ul = min(cl, nl);
  159.         cp += ul;
  160.         nl -= ul;
  161.  
  162.         int uh = min(ch, nh);
  163.         cp += uh;
  164.         nh -= uh;
  165.  
  166.         int us = min({nl, nh, ts});
  167.         cp += us;
  168.  
  169.         int an = bv + ux * 10 + uv * 5 + ui * 1 - 2 * cp;
  170.         cout << an << endl;
  171.     }
  172. }
  173.  
  174. int32_t main() {
  175.     fast_io;
  176.  
  177.     int t;
  178.     cin >> t;
  179.     while (t--) {
  180.         solve();
  181.     }
  182.  
  183.     return 0;
  184. }
Success #stdin #stdout 0s 5320KB
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/DkAhEB
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!