Submission #411575

#TimeUsernameProblemLanguageResultExecution timeMemory
411575nichkeMonochrome Points (JOI20_monochrome)C++14
100 / 100
1229 ms14884 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' int ans; int n; string s; vector<int> a, b; int bit[400005]; void clr() { for (int i = 1; i <= 2 * n; i++) { bit[i] = 0; } } void upd(int v, int k) { while (v <= 2 * n) { bit[v] += k; v += (v & (-v)); } } int qry(int v) { int res = 0; while (v) { res += bit[v]; v -= (v & (-v)); } return res; } int sum(int l, int r) { return qry(r) - qry(l - 1); } int calc(int k) { int res = 0; vector<pair<int, int>> v; for (int i = 0; i < n; i++) { v.push_back({a[i], b[(i + k) % n]}); } for (int i = 0; i < v.size(); i++) { if (v[i].first > v[i].second) { swap(v[i].first, v[i].second); } } sort(v.begin(), v.end()); clr(); for (int i = 0; i < v.size(); i++) { res += sum(v[i].first, v[i].second); upd(v[i].second, 1); } return res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> s; for (int i = 0; i < 2 * n; i++) { if (s[i] == 'W') { a.push_back(i + 1); } else { b.push_back(i + 1); } } ans = max(calc(0), calc(n - 1)); int l = 0, r = n - 2; while (l <= r) { int m = (l + r) / 2; int a = calc(m); int b = calc(m + 1); ans = max(ans, max(a, b)); if (a < b) { l = m + 1; } else { r = m - 1; } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

monochrome.cpp: In function 'long long int calc(long long int)':
monochrome.cpp:45:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
monochrome.cpp:52:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...