제출 #995151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995151		cadmiumsky	Monochrome Points (JOI20_monochrome)	C++17	0 / 100	1 ms	348 KiB

monochrome

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;

#define lsb(x) (x & -x)
struct AIB {
   vector<int> tree;
   void init(int n) { tree.assign(n + 5, 0); }
   void upd(int p, int x) {
      while(p < sz(tree)) tree[p] += x, p += lsb(p);
   }
   int query(int p) {
      int sum = 0;
      while(p > 0) sum += tree[p], p -= lsb(p);
      return sum;
   }
};

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;
   
   queue<int> que[2];
   AIB aib;
   aib.init(n);
   for(int i = 1; i <= n; i++) {
      char ch;
      cin >> ch;
      if(ch == 'B') que[0].emplace(i);
      else que[1].emplace(i);
   }
   
   for(int i = 1; i <= n; i++) aib.upd(i, 1);
   ll sum = 0;
   
   for(int i = 1; i <= n; i++) {
      char ch;
      int P;
      cin >> ch;
      if(ch == 'B') P = que[1].front(), que[1].pop();
      else P = que[0].front(), que[0].pop();
      //cerr << aib.query(n) - aib.query(P);
      sum += aib.query(n) - aib.query(P);
      aib.upd(P, -1);
   }
   cout << sum << '\n';
   
   
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65