제출 #782403

#제출 시각아이디문제언어결과실행 시간메모리
782403tvladm2009Monochrome Points (JOI20_monochrome)C++17
100 / 100
929 ms7548 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = (int) 2e5 + 7; int n; int aib[2 * N]; vector<int> v[2]; string s; void update(int x) { x++; for (int i = x; i < 2 * N; i += i & -i) { aib[i]++; } } int query(int x) { x++; int ret = 0; for (int i = x; i >= 1; i -= i & -i) { ret += aib[i]; } return ret; } int get(int l, int r) { return query(r) - query(l); } ll solve(int offset) { for (int i = 1; i <= 2 * n; i++) { aib[i] = 0; } vector<pair<int, int>> seg; for (int i = 0; i < n; i++) { int j = (i + offset) % n; seg.push_back({v[0][i], v[1][j]}); if (seg.back().first > seg.back().second) { swap(seg.back().first, seg.back().second); } } sort(seg.begin(), seg.end()); ll ret = 0; for (auto &it : seg) { ret += get(it.first, it.second); update(it.second); } return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ///freopen("input", "r", stdin); cin >> n >> s; for (int i = 0; i < 2 * n; i++) { v[(s[i] == 'B')].push_back(i); } int low = 0, high = n - 1, sol = 0; while (low < high) { int mid = (low + high) / 2; if (solve(mid) < solve(mid + 1)) { low = mid + 1; } else { high = mid; } } cout << solve(low) << "\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

monochrome.cpp: In function 'int main()':
monochrome.cpp:63:30: warning: unused variable 'sol' [-Wunused-variable]
   63 |   int low = 0, high = n - 1, sol = 0;
      |                              ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...