Submission #1033050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033050		Unforgettablepl	Chorus (JOI23_chorus)	C++17	100 / 100	5419 ms	63100 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int INF = 1e13;
 
struct fenwick{
	vector<int> tree;
	int n;
	fenwick(int n):n(n),tree(n+1){}
	void add(int k,int x){
		while(k<=n){
			tree[k]+=x;
			k+=k&-k;
		}
	}
	int get(int k){
		int ans = 0;
		while(k){
			ans+=tree[k];
			k-=k&-k;
		}
		return ans;
	}
};
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	s.insert(s.begin(),'$');
	vector<int> posA(n+1);
	vector<int> posB(n+1);
	int cntA = 0,cntB = 0;
	for(int i=1;i<=2*n;i++){
		if(s[i]=='A'){
			posA[++cntA]=i;
		} else {
			posB[++cntB]=i;
		}
	}
	vector<int> costA(n+1);
	vector<int> costB(n+1);
	vector<int> lastB(n+1);
	{
		fenwick temp(2*n);
		for(int i=n;i;i--){
			temp.add(posB[i],1);
			costA[i] = temp.get(posA[i]);
		}
		for(int i=1;i<=n;i++)costA[i]+=costA[i-1];
	}
	{
		fenwick temp(2*n);
		for(int i=n;i;i--){
			costB[i] = n-i-temp.get(posB[i]);
			temp.add(posA[i],1);
		}
		for(int i=1;i<=n;i++)costB[i]+=costB[i-1];
	}
	{
		int currlast = 0;
		for(int i=1;i<=n;i++){
			while(currlast!=n and posB[currlast+1]<posA[i])currlast++;
			lastB[i] = min(currlast,i);
		}
	}
	auto solve = [&](int penalty){
		vector<pair<int,int>> DP(n+1,{INF,INF});
		DP[0]={0,0};
		auto cost = [&](int a,int b){
			assert(a<=b);
			int Ac = costA[b]-costA[a-1];
			if(lastB[b]<a)return Ac+penalty;
			int amt = lastB[b]-a+1;;
			int Bc = costB[lastB[b]]-costB[a-1]-amt*(n-b);
			return Ac+Bc+penalty;
		};
		deque<pair<int,int>> q;
		auto test = [&](int x,int a,int b){
			// Will return true if a is better for x than b
			return make_pair(DP[a-1].first+cost(a,x),DP[a-1].second+1)<make_pair(DP[b-1].first+cost(b,x),DP[b-1].second+1);
		};
		for(int i=1;i<=n;i++){
			// Add i
			while(!q.empty() and q.front().second<i)q.pop_front();
			while(!q.empty()){
				int lower = i;
				if(q.size()>1)lower = q[q.size()-2].second+1;
				if(test(lower,i,q.back().first)){
					q.pop_back();
					continue;
				}
				for(int jump=524288;jump;jump/=2)if(lower+jump<=n and test(lower+jump,q.back().first,i))lower+=jump;
				q.back().second = lower;
				break;
			}
			if(q.empty() or q.back().second!=n)q.emplace_back(i,n);
			// Query i
			assert(!q.empty());
			DP[i] = {DP[q.front().first-1].first+cost(q.front().first,i),DP[q.front().first-1].second+1};
		}
		return DP[n];
	};
	int best_penalty = -1;
	for(int jump=(1ll<<40);jump;jump/=2ll){
		if(solve(best_penalty+jump).second>k)best_penalty+=jump;
	}
	best_penalty++;
	cout << solve(best_penalty).first-k*best_penalty << '\n';
}

Compilation message (stderr)

chorus.cpp: In constructor 'fenwick::fenwick(long long int)':
chorus.cpp:10:6: warning: 'fenwick::n' will be initialized after [-Wreorder]
   10 |  int n;
      |      ^
chorus.cpp:9:14: warning:   'std::vector<long long int> fenwick::tree' [-Wreorder]
    9 |  vector<int> tree;
      |              ^~~~
chorus.cpp:11:2: warning:   when initialized here [-Wreorder]
   11 |  fenwick(int n):n(n),tree(n+1){}
      |  ^~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 26 / 26
• Subtask 5: 13 / 13