Submission #997008

#	Time	Username	Problem	Language	Result	Execution time	Memory
997008		cadmiumsky	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1243 ms	17296 KiB

monochrome

// problema stupida
// ok dupa asta promit ca ma gandesc serios la problema
#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;
   }
};



int n;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // trebuia sa o incerc
ll init(string s, int a = rng() % (2 * n + 1)) {
   vector<pii> segm;
   vector<int> b, w;
   for(int i = 0; i < sz(s); i++)
      (s[i] == 'B'? b : w).emplace_back(i + 1);
   
   for(int i = 0; i < sz(b); i++)
      segm.emplace_back(b[i], w[(i + a) % sz(w)]);
   for(auto &[l, r] : segm) {
      if(l > r) swap(l, r);
   }
   
   sort(all(segm));
   ll sum = 0;
   AIB aib;
   aib.init(sz(s) + 5);
   for(auto [l, r] : segm) {
      sum += aib.query(r) - aib.query(l);
      aib.upd(r, 1);
   }
   return sum;
}


signed main() {
   ld S = clock();
   cin.tie(0) -> sync_with_stdio(0);
   cin >> n;
   
   string s;
   cin >> s;
   ll rez = 0;
   
   int lim = -1;
   for(int i = 20; i >= 0; i--) {
      if(init(s, lim + (1 << i)) <= init(s, lim + (1 << i) + 1)) lim += (1 << i);
   }
   
   cout << init(s, lim + 1) << '\n';
      
}

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

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:61:7: warning: unused variable 'S' [-Wunused-variable]
   61 |    ld S = clock();
      |       ^
monochrome.cpp:67:7: warning: unused variable 'rez' [-Wunused-variable]
   67 |    ll rez = 0;
      |       ^~~

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