Submission #292895

#	Time	Username	Problem	Language	Result	Execution time	Memory
292895		limabeans	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2096 ms	36084 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<<": "<<res<<endl;
	//cout<<iter<<": "<<eval_brute(v)<<" "<<res<<endl;
	best = max(best, res);
	std::rotate(W.begin(), W.begin()+1, W.end());
    }
    
    return best;
}

vector<pair<int,int>> make(vector<int> B, vector<int> W) {
    vector<pair<int,int>> v;
    for (int i=0; i<n/2; i++) {
	int x=B[i];
	int y=W[i];
	if (x>y) swap(x,y);
	v.push_back({x,y});

    }
    return v;
}

vector<int> rota(vector<int> W, int r) {
    std::rotate(W.begin(), W.begin()+r, W.end());
    return W;
}

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

    // if (n<=10) {
    // 	out(brute());
    // }

    vector<int> B, W;
    for (int i=0; i<n; i++) {
	if (s[i]=='B') B.push_back(i); else W.push_back(i);
    }
    auto ivals = make(B, W);
    auto W1 = rota(W, 1);
    auto ivals1 = make(B, W1);


    ll best = eval(ivals);

    int lo = 0;
    int hi = n/2;

    // dips first
    if (eval(ivals) >= eval(ivals1)) {
	int L = 0;
	int R = n/2;
	while (R-L>1) {
	    int M = (L+R)/2;
	    auto w1 = rota(W,M);
	    auto w2 = rota(W,M+1);
	    ll tmp1 = eval(make(B,w1));
	    ll tmp2 = eval(make(B,w2));
	    best = max({best, tmp1, tmp2});
	    if (tmp1>=tmp2) {
		L = M;
	    } else {
		R = M;
	    }
	}

	lo = L+1;
    }

    // watch(lo);
    // watch(hi);

    while (hi-lo>1) {
	int mid=(lo+hi)/2;
	auto w1 = rota(W,mid);
	auto w2 = rota(W,mid+1);
	ll tmp1 = eval(make(B,w1));
	ll tmp2 = eval(make(B,w2));
	best = max({best, tmp1, tmp2});

	if (tmp1<=tmp2) {
	    lo = mid;
	} else {
	    hi = mid;
	}
    }

    // watch(brute());
    // assert(best==brute());
    cout<<best<<endl;
       
    return 0;
}

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