Advertisement
ivnikkk

Untitled

Dec 28th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.31 KB | None | 0 0
  1. #include <vector>
  2. #include<iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include<math.h>
  18. using namespace std;
  19. typedef unsigned int ui;
  20. typedef long long             ll;
  21. typedef unsigned long long     ull;
  22. typedef long double            ld;
  23. #define endl              "\n"
  24. #define all(a)            a.begin(), a.end()
  25. #define allr(a)           a.rbegin(), a.rend()
  26. #define pb                push_back
  27. #define pikachu           push_back
  28. #define F                 first
  29. #define S                 second
  30. ll inf = 1e18;
  31. ld eps = 1e-6;
  32. const ll MAXN = 5e4 + 1;/*
  33. ll add[MAXN];
  34. ll t[4 * MAXN];
  35. ll a[MAXN];
  36. ll n;
  37. void push(ll v, ll vl, ll vr) {
  38.     if (vl != vr) {
  39.         add[2 * v] += add[v];
  40.         add[2 * v + 1] += add[v];
  41.     }
  42.     t[v] += add[v] * (vr - vl + 1);
  43.     add[v] = 0;
  44. }
  45. void build(ll v, ll tl, ll tr) {
  46.     if (tl == tr)
  47.         t[v] = a[tl];
  48.     else {
  49.         ll tm = (tl + tr) / 2;
  50.         build(v * 2, tl, tm);
  51.         build(v * 2 + 1, tm + 1, tr);
  52.         t[v] = t[v * 2] + t[v * 2 + 1];
  53.     }
  54. }
  55.  
  56. void update(ll v, ll vl, ll vr, ll l, ll r, ll val) {
  57.     push(v, vl, vr);
  58.     if (r < vl || vr < l)
  59.         return;
  60.     if (l <= vl && vr <= r) {
  61.         add[v] += val;
  62.         push(v, vl, vr);
  63.         return;
  64.     }
  65.     ll vm = vl + (vr - vl) / 2;
  66.     update(2 * v + 1, vl, vm, l, r, val);
  67.     update(2 * v + 2, vm + 1, vr, l, r, val);
  68.     t[v] = t[2 * v + 1] + t[2 * v + 2];
  69. }
  70.  
  71. ll sum(ll v, ll vl, ll vr, ll l, ll r) {
  72.     push(v, vl, vr);
  73.     if (r < vl || vr < l)
  74.         return 0;
  75.     if (l <= vl && vr <= r)
  76.         return t[v];
  77.     ll vm = vl + (vr - vl) / 2;
  78.     ll ql = sum(2 * v, vl, vm, l, r);
  79.     ll qr = sum(2 * v + 1, vm + 1, vr, l, r);
  80.     return ql * ql + qr * qr;
  81. }*/
  82. //const ll c = 300;
  83. //ll ans[MAXN];
  84. //struct query {
  85. //    ll l, r, x, y, ind;
  86. //};
  87. //vector<query> b[c];
  88. //
  89. //struct sub_str {
  90. //    ll l, r, add, ind;
  91. //};
  92.  
  93. ll check(vector <ll>& a, ll key) {
  94.     ll l = 0, r = a.size();
  95.     ll m;
  96.     while (r - l > 1) {
  97.         m = (l + r) / 2;
  98.         if (a[m] <= key) {
  99.             l = m;
  100.         }
  101.         else {
  102.             r = m;
  103.         }
  104.     }
  105.     return l;
  106. }
  107. void solve() {}
  108. signed main() {
  109.     ios_base::sync_with_stdio(false);
  110.     cin.tie(nullptr);
  111.     ll t = 1;
  112.     //cin >> t;
  113.     while (t--) {
  114.        // ll n, m, q;
  115.        // cin >> n >> m >> q;
  116.        // vector<ll> a(n);
  117.        // for (ll i = 0; i < n; i++) {
  118.        //     cin >> a[i];
  119.        //     //a[i]*=a[i];
  120.        // }
  121.        //// build(1, 0, n - 1);
  122.        // vector<sub_str> q_sum;
  123.        // for (ll i = 0; i < m; i++) {
  124.        //     ll l, r;
  125.        //     ll add;
  126.        //     cin >> l >> r >> add;
  127.        //     l--, r--;
  128.        //     q_sum.pb({ l,r,add,i + 1 });
  129.        //     /*
  130.        //     update(1, 0, n - 1, l, r, add);
  131.        //     cout << sum(1, 0, n - 1, l, r);*/
  132.        // }
  133.        // for (ll i = 0; i < q; i++) {
  134.        //     ll l, r, x, y;
  135.        //     cin >> l >> r >> x >> y;
  136.        //     l--, r--, x--, y--;
  137.        //     b[x / c].push_back({ l,r,x,y,i });
  138.        // }
  139.        // for (ll i = 0; i < c; i++) {
  140.        //     sort(b[i].begin(), b[i].end(), [](query a, query b) {
  141.        //         return a.y < b.y;
  142.        //         });
  143.        // }
  144.  
  145.        // for (ll i = 0; i < c; i++) {
  146.        //     ll l = i * c, r = i * c - 1;
  147.        //     for (query q : b[i]) {
  148.        //         ll pre_ans = 0;
  149.        //         while (r < q.y) {
  150.        //             ////++r
  151.        //             //update(1, 0, n - 1, q_sum[++r].l, q_sum[r].r, q_sum[r].add);
  152.        //             //pre_ans += sum(1, 0, n - 1, q.l, q.r);
  153.        //             ll summ = 0;
  154.        //             for (ll i = q_sum[++r].l; i <= q_sum[r].r; i++) {
  155.        //             }
  156.        //         }
  157.        //         while (l < q.x) {
  158.        //             ////l++
  159.        //             //update(1, 0, n - 1, q_sum[l].l, q_sum[l].r, -q_sum[l].add);
  160.        //             //pre_ans += sum(1, 0, n - 1, q.l, q.r);
  161.        //             ll summ = 0;
  162.        //             for (ll i = q_sum[l].l; i <= q_sum[l].r; i++) {
  163.        //             }
  164.        //             l++;
  165.        //         }
  166.        //         while (l > q.x) {
  167.        //             //--l
  168.        //             if (l - 1 >= 0) {
  169.        //              /*   update(1, 0, n - 1, q_sum[--l].l, q_sum[l].r, q_sum[l].add);
  170.        //                 pre_ans += sum(1, 0, n - 1, q.l, q.r);*/
  171.        //                 ll summ = 0;
  172.        //                 for (ll i = q_sum[--l].l; i <= q_sum[l].r; i++) {
  173.        //                 }
  174.        //             }
  175.        //         }
  176.        //         ll mod = 1e9 + 7;
  177.        //         if (l != -1) {
  178.        //             l = 0;
  179.        //             for (ll i = q.l; i <= q.r; i++) {
  180.        //                 pre_ans += a[i] * a[i] % mod;
  181.        //             }
  182.        //         }
  183.        //         vector<ll> sub = a;
  184.        //         for (ll k = l; k <= r; k++) {
  185.        //             for (ll j = q_sum[k].l; j <= q_sum[k].r; j++) {
  186.        //                 if (j >= q.l && j <= q.r) {
  187.        //                     sub[j] += q_sum[k].add%mod;
  188.        //                 }
  189.        //             }
  190.        //             for (ll i = q.l; i <= q.r; i++) {
  191.        //                 pre_ans += sub[i]*sub[i]%mod;
  192.        //             }
  193.        //         }
  194.        //        
  195.        //         ans[q.ind] = pre_ans;
  196.        //     }
  197.        // }
  198.        // for (ll i = 0; i < q; i++) {
  199.        //     cout << ans[i] << endl;
  200.        // }
  201.         string s;
  202.         ll n, i, j, ans = 0, now, next;
  203.         cin >> s;
  204.         vector <ll> U, S;
  205.         for (i = 0; i < s.size(); i++) {
  206.             if (s[i] == 'U') {
  207.                 U.push_back(i);
  208.             }
  209.             else {
  210.                 S.push_back(i);
  211.             }
  212.         }
  213.         for (i = 0; i < s.size(); i++) {
  214.             if (s[i] == 'U') {
  215.                 ll id = check(U, i), l, r;
  216.                 if (id == 0) {
  217.                     l = i;
  218.                     if (id + 1 < U.size()) {
  219.                         r = U[id + 1] - i - 1;
  220.                     }
  221.                     else {
  222.                         r = s.size() - i - 1;;
  223.                         //ussssssss
  224.                     }
  225.                     if (l > -1 && r > 1) {
  226.                         ans += (r - 1);
  227.                     }
  228.                     if (l > 0 && r > 0) {
  229.                         ans += r;
  230.                     }
  231.                     if (l > 1) {
  232.                         ans += (l - 1) * (r + 1);
  233.                     }
  234.                 }
  235.                 else if (id == U.size() - 1) {
  236.                     r = s.size() - i - 1;
  237.                     l = i - U[id - 1] - 1;
  238.                     if (l > -1 && r > 1) {
  239.                         ans += (r - 1);
  240.                     }
  241.                     if (l > 0 && r > 0) {
  242.                         ans += r;
  243.                     }
  244.                     if (l > 1) {
  245.                         ans += (l - 1) * (r + 1);
  246.                     }
  247.                 }
  248.                 else {
  249.                     r = U[id + 1] - i - 1;
  250.                     l = i - U[id - 1] - 1;
  251.                     if (l > -1 && r > 1) {
  252.                         ans += (r - 1);
  253.                     }
  254.                     if (l > 0 && r > 0) {
  255.                         ans += r;
  256.                     }
  257.                     if (l > 1) {
  258.                         ans += (l - 1) * (r + 1);
  259.                     }
  260.                 }
  261.             }
  262.             else {
  263.                 ll id = check(S, i), l, r;
  264.                 if (id == 0) {
  265.                     l = i;
  266.                     if (id + 1 < S.size()) {
  267.                         r = S[id + 1] - i - 1;
  268.                     }
  269.                     else {
  270.                         r = s.size() - i - 1;;
  271.                     }
  272.                     if (l > -1 && r > 1) {
  273.                         ans += (r - 1);
  274.                     }
  275.                     if (l > 0 && r > 0) {
  276.                         ans += r;
  277.                     }
  278.                     if (l > 1) {
  279.                         ans += (l - 1) * (r + 1);
  280.                     }
  281.                 }
  282.                 else if (id == S.size() - 1) {
  283.                     r = s.size() - i - 1;
  284.                     l = i - S[id - 1] - 1;
  285.                     if (l > -1 && r > 1) {
  286.                         ans += (r - 1);
  287.                     }
  288.                     if (l > 0 && r > 0) {
  289.                         ans += r;
  290.                     }
  291.                     if (l > 1) {
  292.                         ans += (l - 1) * (r + 1);
  293.                     }
  294.                 }
  295.                 else {
  296.                     r = S[id + 1] - i - 1;
  297.                     l = i - S[id - 1] - 1;
  298.                     if (l > -1 && r > 1) {
  299.                         ans += (r - 1);
  300.                     }
  301.                     if (l > 0 && r > 0) {
  302.                         ans += r;
  303.                     }
  304.                     if (l > 1) {
  305.                         ans += (l - 1) * (r + 1);
  306.                     }
  307.                 }
  308.             }
  309.         }
  310.         cout << ans << endl;
  311.     }
  312. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement