Submission #292893

#	Time	Username	Problem	Language	Result	Execution time	Memory
292893		limabeans	Monochrome Points (JOI20_monochrome)	C++17	25 / 100	2041 ms	928 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;




int n;
string s;
bool used[maxn];

template<typename T> struct bit1 {
    T add(T x, T y) {
	return x+y;
    }
    int n;
    vector<T> t;
    void init(int n) {
	this->n=n;
	t.resize(n+10);
    }
    T qry(int i) {
	T res=0;
	for (; i>0; i-=i&-i) res=add(res,t[i]);
	return res;
    }
    void upd(int i, T dx) {
	assert(i>=1 && i<=n);
	for (; i<=n; i+=i&-i) t[i]=add(t[i],dx);
    }
};


bool isect(pair<int,int> p, pair<int,int> q) {
    if (max(p.first,q.first) >= min(p.second,q.second)) return false;
    if (p.first>q.first) swap(p,q);
    if (p.first<=q.first && q.second<=p.second) return false;
    return true;
}

ll eval_brute(vector<pair<int,int>> v) {
    assert(int(v.size())==n/2);
    for (auto &p: v) {
	if (p.first>p.second) {
	    swap(p.first,p.second);
	}
    }
    ll res = 0;
    
    for (int i=0; i<n/2; i++) {
	for (int j=i+1; j<n/2; j++) {
	    if (isect(v[i],v[j])) res++;
	}
    }

    return res;

    
}


ll eval(vector<pair<int,int>> v) {
    assert(int(v.size())==n/2);
    int N = 0;
    vector<pair<int,int>> ev;
    map<int,int> close, open;
    for (auto &p: v) {
	if (p.first>p.second) {
	    swap(p.first,p.second);
	}
	p.first++;
	p.second++;
	N = max(N, p.second);
	ev.push_back({p.first,0});
	ev.push_back({p.second,1});
	close[p.first]=p.second;
	open[p.second]=p.first;
    }
			
    ll res = 0;
    bit1<ll> bit;
    bit.init(N);

    sort(ev.begin(), ev.end());
    
    for (auto p: ev) {
	if (p.second==0) {
	    bit.upd(p.first,+1);
	}
	if (p.second==1) {
	    bit.upd(open[p.first],-1);
	    int l = open[p.first];
	    int r = p.first;
	    assert(l<=r);
	    res += (bit.qry(r)-bit.qry(l-1));
	}
    }

    return res;
}

ll brute() {
    ll best=0;
    vector<int> B, W;
    for (int i=0; i<n; i++) {
	if (s[i]=='B') B.push_back(i); else W.push_back(i);
    }

    for (int iter=0; iter<n/2; iter++) {
	vector<pair<int,int>> v;
	for (int i=0; i<n/2; i++) {
	    v.push_back({B[i],W[i]});
	}
	ll res = eval(v);
	//cout<<iter<<": "<<eval_brute(v)<<" "<<res<<endl;
	best = max(best, res);
	std::rotate(W.begin(), W.begin()+1, W.end());
    }
    
    return best;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>s;
    n *= 2;

    cout<<brute()<<endl;
    
       
    return 0;
}

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