fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define PhTrNghia "SLUCKY"
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2e5 + 5;
  9. const int inf = 1e18;
  10.  
  11. struct fenwick_tree{
  12.     int n;
  13.     vector <int> tree;
  14.     fenwick_tree(int _n){
  15.         n = _n;
  16.         tree.assign(n + 5, 0);
  17.     }
  18.  
  19.     void update(int pos, int val){
  20.         for (; pos <= n; pos += -pos&pos) tree[pos] += val;
  21.     }
  22.  
  23.     int get(int pos){
  24.         int res = 0;
  25.         for (; pos; pos -= -pos&pos) res += tree[pos];
  26.         return res;
  27.     }
  28.  
  29.     int get(int l, int r){
  30.         if (l > r) return 0;
  31.         return get(r) - get(l - 1);
  32.     }
  33. };
  34.  
  35. struct segtree{
  36.     int n;
  37.     vector <int> tree;
  38.     segtree (int _n){
  39.         n = _n;
  40.         tree.assign(n << 2 | 3, 0);
  41.     }
  42.     void update(int id, int l, int r, int pos, int val){
  43.         if (r < pos or l > pos) return;
  44.         if (l == r){
  45.             tree[id] = val;
  46.             return;
  47.         }
  48.         int mid = (l + r) >> 1;
  49.         update(id << 1, l, mid, pos, val);
  50.         update(id << 1 | 1, mid + 1, r, pos, val);
  51.         tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
  52.     }
  53.  
  54.     int get(int id, int l, int r, int u, int v){
  55.         if (l > v or r < u) return -inf;
  56.         if (l >= u && r <= v) return tree[id];
  57.         int mid = (l + r) >> 1;
  58.         int get1 = get(id << 1, l, mid, u, v);
  59.         int get2 = get(id << 1 | 1, mid + 1, r, u, v);
  60.         return max(get1, get2);
  61.     }   
  62.  
  63.     void update(int pos, int val){
  64.         update(1, 1, n, pos, val);
  65.     }
  66.  
  67.     int get(int l, int r){
  68.         return get(1, 1, n, l, r);
  69.     }
  70. };
  71.  
  72. stack <int> st;
  73. int n, ans = 0;
  74. string s;
  75. vector <pair <int, int>> layer[maxn];
  76.  
  77. signed main(){
  78.     ios_base::sync_with_stdio(false);
  79.     cin.tie(0); cout.tie(0);
  80.     if (fopen(PhTrNghia".INP", "r")){
  81.         freopen(PhTrNghia".INP", "r", stdin);
  82.         freopen(PhTrNghia".OUT", "w", stdout);
  83.     }
  84.     cin >> n >> s;
  85.     s = "$" + s;
  86.  
  87.     segtree smt(n);
  88.     int mx_layer = -inf;
  89.     for (int i = 1; i <= n; i++){
  90.         if (!st.empty() && s[i] == '8' && s[st.top()] == '6'){
  91.             int mx = smt.get(st.top(), i);
  92.             smt.update(st.top(), mx+1);
  93.             layer[mx+1].push_back({st.top(), i});
  94.             mx_layer = max(mx_layer, mx+1);
  95.             st.pop();
  96.             continue;
  97.         }
  98.         st.push(i);
  99.     }
  100.  
  101.     fenwick_tree bit(n);
  102.     for (int i = 1; i <= mx_layer; i++){
  103.         for (pair <int, int> cur: layer[i]){
  104.             int l = cur.first;
  105.             int r = cur.second;
  106.             int cnt = bit.get(l-1);
  107.             ans += (l - (cnt << 1));
  108.         }
  109.  
  110.         for (pair <int, int> cur: layer[i]){
  111.             int l = cur.first;
  112.             bit.update(l, 1);
  113.         }
  114.     }
  115.     cout << ans;
  116.     return 0;
  117. }
  118. /*
  119.  
  120. */
  121.  
Success #stdin #stdout 0.01s 8240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C3vVeR
language:
C++14 (gcc 8.3)
created:
4 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!