Submission #1038749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038749		phong	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1508 ms	38612 KiB

monochrome

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 4e5 + 5, N = 1e5;
const ll oo = 1e9;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int n;
string s;
vector<int> one, two;
vector<pii> tmp;
struct holder{
    vector<int> tmp;
    int f[nmax];

    void update(int x, int val){
        for(; x <= 2 *n; x += x&-x) f[x] += val, tmp.push_back(x);
    }
    int get(int x){
        int res = 0;
        for(; x ; x -= x&-x) res += f[x];
        return res;
    }
    void clear(){
        for(auto p : tmp) f[p] = 0;
        tmp.clear();
    }
}F, G;
ll get(int x){
    tmp.clear();
    for(int i = 0; i < n; ++i){
        int u = one[i];
        int v = two[(i + x + n * 10) % n];
        if(u > v) swap(u, v);
        tmp.push_back({u, v});
//        cout << u << ' ' << v << endl;
    }
    sort(tmp.begin(), tmp.end());
//    for(auto [u, v] : tmp) cout << u << ' ' << v << endl;
    ll ans = 0;
    for(int i = tmp.size() - 1; i >= 0; --i){
        ans += G.get(tmp[i].se) - F.get(tmp[i].se);
        F.update(tmp[i].se, 1);
        G.update(tmp[i].fi, 1);
    }
    F.clear();G.clear();
    return ans;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> n;
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == 'W') one.push_back(i + 1);
        else two.push_back(i + 1);
    }
//    cout << get(0);
//    for(int i = 0; i < n; ++i) cout << get(i) << ' ';
    int l = 0, r = n - 2, kq = -1;
    while(l <= r){
        int mid = r + l >> 1;
        if(get(mid) <= get(mid + 1)){
            kq = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    ll ans = 0;
    for(int i = kq - 10; i <= kq + 10; ++i) ans = max(ans, get(i));
    cout << ans;

}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5

4
2 1 5 3
1
1 4


*/

Compilation message (stderr)

monochrome.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < s.size(); ++i){
      |                    ~~^~~~~~~~~~
monochrome.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = r + l >> 1;
      |                   ~~^~~

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