Submission #643615

#TimeUsernameProblemLanguageResultExecution timeMemory
643615maomao90Monochrome Points (JOI20_monochrome)C++17
4 / 100
9 ms468 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 400005; int n; string s; ll ans; int fw[MAXN]; void incre(int i, int x) { for (; i <= 2 * n; i += i & -i) { fw[i] += x; } } int qsm(int i) { int res = 0; for (; i > 0; i -= i & -i) { res += fw[i]; } return res; } int qsm(int s, int e) { return qsm(e) - qsm(s - 1); } int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n; cin >> s; s = "?" + s; vll vec; REP (i, 2, 2 * n + 1) { if (s[i] == s[1]) { continue; } int u = 1, v = i; vii eg; cerr << u << ' ' << v << '\n'; while (u <= 2 * n) { eg.pb({u, v}); cerr << ' ' << u << ' ' << v << '\n'; u++; v++; while (u <= 2 * n && s[u] != s[1]) { u++; } if (v > 2 * n) { v -= 2 * n; } while (s[v] == s[1]) { v++; if (v > 2 * n) { v -= 2 * n; } } } assert(SZ(eg) == n); for (auto &[u, v] : eg) { if (u > v) { swap(u, v); } } sort(ALL(eg)); REP (i, 1, 2 * n + 1) { fw[i] = 0; } ll sm = 0; for (auto [u, v] : eg) { sm += qsm(u, v); incre(v, 1); } mxto(ans, sm); cerr << ' ' << sm << '\n'; vec.pb(sm); } bool dec = 0; bool can = 1; REP (i, 1, SZ(vec)) { //assert(vec[i] != vec[i - 1]); if (vec[i] < vec[i - 1]) { dec = 1; } else if (dec) { can = 0; break; } } bool can2 = 1; dec = 0; REP (i, 1, SZ(vec)) { //assert(vec[i] != vec[i - 1]); if (vec[i] > vec[i - 1]) { dec = 1; } else if (dec) { can2 = 0; break; } } assert(can || can2); cout << ans << '\n'; return 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...