제출 #995166

#제출 시각아이디문제언어결과실행 시간메모리
995166cadmiumskyMonochrome Points (JOI20_monochrome)C++17
35 / 100
1612 ms3652 KiB
#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() % (sz(s) + 1); s = s.substr(a) + s.substr(0, a); stringstream haha; haha << s; queue<int> que[2]; AIB aib; aib.init(n); for(int i = 1; i <= n; i++) { char ch; haha >> 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; haha >> ch; if(ch == 'B') P = que[1].front(), que[1].pop(); else P = que[0].front(), que[0].pop(); sum += aib.query(n) - aib.query(P); aib.upd(P, -1); } return sum; } signed main() { ld S = clock(); cin.tie(0) -> sync_with_stdio(0); cin >> n; string s; cin >> s; ll rez = 0; while(clock() - S < (ld)CLOCKS_PER_SEC * 1.6) rez = max(rez, init(s)); cout << rez << '\n'; } /** Istenem! Nu poate fi real. -- Surse verificate */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...