Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include<iostream>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- #include<math.h>
- using namespace std;
- typedef unsigned int ui;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define endl "\n"
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define pb push_back
- #define pikachu push_back
- #define F first
- #define S second
- ll inf = 1e18;
- ld eps = 1e-6;
- const ll MAXN = 5e4 + 1;/*
- ll add[MAXN];
- ll t[4 * MAXN];
- ll a[MAXN];
- ll n;
- void push(ll v, ll vl, ll vr) {
- if (vl != vr) {
- add[2 * v] += add[v];
- add[2 * v + 1] += add[v];
- }
- t[v] += add[v] * (vr - vl + 1);
- add[v] = 0;
- }
- void build(ll v, ll tl, ll tr) {
- if (tl == tr)
- t[v] = a[tl];
- else {
- ll tm = (tl + tr) / 2;
- build(v * 2, tl, tm);
- build(v * 2 + 1, tm + 1, tr);
- t[v] = t[v * 2] + t[v * 2 + 1];
- }
- }
- void update(ll v, ll vl, ll vr, ll l, ll r, ll val) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return;
- if (l <= vl && vr <= r) {
- add[v] += val;
- push(v, vl, vr);
- return;
- }
- ll vm = vl + (vr - vl) / 2;
- update(2 * v + 1, vl, vm, l, r, val);
- update(2 * v + 2, vm + 1, vr, l, r, val);
- t[v] = t[2 * v + 1] + t[2 * v + 2];
- }
- ll sum(ll v, ll vl, ll vr, ll l, ll r) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return 0;
- if (l <= vl && vr <= r)
- return t[v];
- ll vm = vl + (vr - vl) / 2;
- ll ql = sum(2 * v, vl, vm, l, r);
- ll qr = sum(2 * v + 1, vm + 1, vr, l, r);
- return ql * ql + qr * qr;
- }*/
- //const ll c = 300;
- //ll ans[MAXN];
- //struct query {
- // ll l, r, x, y, ind;
- //};
- //vector<query> b[c];
- //
- //struct sub_str {
- // ll l, r, add, ind;
- //};
- ll check(vector <ll>& a, ll key) {
- ll l = 0, r = a.size();
- ll m;
- while (r - l > 1) {
- m = (l + r) / 2;
- if (a[m] <= key) {
- l = m;
- }
- else {
- r = m;
- }
- }
- return l;
- }
- void solve() {}
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- ll t = 1;
- //cin >> t;
- while (t--) {
- // ll n, m, q;
- // cin >> n >> m >> q;
- // vector<ll> a(n);
- // for (ll i = 0; i < n; i++) {
- // cin >> a[i];
- // //a[i]*=a[i];
- // }
- //// build(1, 0, n - 1);
- // vector<sub_str> q_sum;
- // for (ll i = 0; i < m; i++) {
- // ll l, r;
- // ll add;
- // cin >> l >> r >> add;
- // l--, r--;
- // q_sum.pb({ l,r,add,i + 1 });
- // /*
- // update(1, 0, n - 1, l, r, add);
- // cout << sum(1, 0, n - 1, l, r);*/
- // }
- // for (ll i = 0; i < q; i++) {
- // ll l, r, x, y;
- // cin >> l >> r >> x >> y;
- // l--, r--, x--, y--;
- // b[x / c].push_back({ l,r,x,y,i });
- // }
- // for (ll i = 0; i < c; i++) {
- // sort(b[i].begin(), b[i].end(), [](query a, query b) {
- // return a.y < b.y;
- // });
- // }
- // for (ll i = 0; i < c; i++) {
- // ll l = i * c, r = i * c - 1;
- // for (query q : b[i]) {
- // ll pre_ans = 0;
- // while (r < q.y) {
- // ////++r
- // //update(1, 0, n - 1, q_sum[++r].l, q_sum[r].r, q_sum[r].add);
- // //pre_ans += sum(1, 0, n - 1, q.l, q.r);
- // ll summ = 0;
- // for (ll i = q_sum[++r].l; i <= q_sum[r].r; i++) {
- // }
- // }
- // while (l < q.x) {
- // ////l++
- // //update(1, 0, n - 1, q_sum[l].l, q_sum[l].r, -q_sum[l].add);
- // //pre_ans += sum(1, 0, n - 1, q.l, q.r);
- // ll summ = 0;
- // for (ll i = q_sum[l].l; i <= q_sum[l].r; i++) {
- // }
- // l++;
- // }
- // while (l > q.x) {
- // //--l
- // if (l - 1 >= 0) {
- // /* update(1, 0, n - 1, q_sum[--l].l, q_sum[l].r, q_sum[l].add);
- // pre_ans += sum(1, 0, n - 1, q.l, q.r);*/
- // ll summ = 0;
- // for (ll i = q_sum[--l].l; i <= q_sum[l].r; i++) {
- // }
- // }
- // }
- // ll mod = 1e9 + 7;
- // if (l != -1) {
- // l = 0;
- // for (ll i = q.l; i <= q.r; i++) {
- // pre_ans += a[i] * a[i] % mod;
- // }
- // }
- // vector<ll> sub = a;
- // for (ll k = l; k <= r; k++) {
- // for (ll j = q_sum[k].l; j <= q_sum[k].r; j++) {
- // if (j >= q.l && j <= q.r) {
- // sub[j] += q_sum[k].add%mod;
- // }
- // }
- // for (ll i = q.l; i <= q.r; i++) {
- // pre_ans += sub[i]*sub[i]%mod;
- // }
- // }
- //
- // ans[q.ind] = pre_ans;
- // }
- // }
- // for (ll i = 0; i < q; i++) {
- // cout << ans[i] << endl;
- // }
- string s;
- ll n, i, j, ans = 0, now, next;
- cin >> s;
- vector <ll> U, S;
- for (i = 0; i < s.size(); i++) {
- if (s[i] == 'U') {
- U.push_back(i);
- }
- else {
- S.push_back(i);
- }
- }
- for (i = 0; i < s.size(); i++) {
- if (s[i] == 'U') {
- ll id = check(U, i), l, r;
- if (id == 0) {
- l = i;
- if (id + 1 < U.size()) {
- r = U[id + 1] - i - 1;
- }
- else {
- r = s.size() - i - 1;;
- //ussssssss
- }
- if (l > -1 && r > 1) {
- ans += (r - 1);
- }
- if (l > 0 && r > 0) {
- ans += r;
- }
- if (l > 1) {
- ans += (l - 1) * (r + 1);
- }
- }
- else if (id == U.size() - 1) {
- r = s.size() - i - 1;
- l = i - U[id - 1] - 1;
- if (l > -1 && r > 1) {
- ans += (r - 1);
- }
- if (l > 0 && r > 0) {
- ans += r;
- }
- if (l > 1) {
- ans += (l - 1) * (r + 1);
- }
- }
- else {
- r = U[id + 1] - i - 1;
- l = i - U[id - 1] - 1;
- if (l > -1 && r > 1) {
- ans += (r - 1);
- }
- if (l > 0 && r > 0) {
- ans += r;
- }
- if (l > 1) {
- ans += (l - 1) * (r + 1);
- }
- }
- }
- else {
- ll id = check(S, i), l, r;
- if (id == 0) {
- l = i;
- if (id + 1 < S.size()) {
- r = S[id + 1] - i - 1;
- }
- else {
- r = s.size() - i - 1;;
- }
- if (l > -1 && r > 1) {
- ans += (r - 1);
- }
- if (l > 0 && r > 0) {
- ans += r;
- }
- if (l > 1) {
- ans += (l - 1) * (r + 1);
- }
- }
- else if (id == S.size() - 1) {
- r = s.size() - i - 1;
- l = i - S[id - 1] - 1;
- if (l > -1 && r > 1) {
- ans += (r - 1);
- }
- if (l > 0 && r > 0) {
- ans += r;
- }
- if (l > 1) {
- ans += (l - 1) * (r + 1);
- }
- }
- else {
- r = S[id + 1] - i - 1;
- l = i - S[id - 1] - 1;
- if (l > -1 && r > 1) {
- ans += (r - 1);
- }
- if (l > 0 && r > 0) {
- ans += r;
- }
- if (l > 1) {
- ans += (l - 1) * (r + 1);
- }
- }
- }
- }
- cout << ans << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement