提出 #31435255

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

struct Func{ long long x=0, c=0; };
Func& operator+=(Func& l, Func r){ l.x += r.x; l.c += r.c; return l; }
Func& operator-=(Func& l, Func r){ l.x -= r.x; l.c -= r.c; return l; }
Func operator+(Func l, Func r){ return l += r; }
Func operator-(Func l, Func r){ return l -= r; }

int main() {
	string S; cin >> S;
	int N = S.size();
	int L; cin >> L;

	int cnt = (L + 1) / 2;{
		int c = 0;
		rep(i,N) if(S[i] == '(') c++;
		if(c < cnt){
			rep(k,N-L+1) cout << "-1\n";
			return 0;
		}
	}

	vector<int> posA;
	vector<int> posB;
	rep(i,N) if(S[i] == '('){
		int c = posA.size();
		posA.push_back(i - 2 * c);
		posB.push_back(i - c);
	}

	int k = 0;
	int posL = 0;

	vector<Func> rqA(N*2);
	vector<Func> rqB(N*2);
	Func sum_rqA;
	Func sum_rqB;

	auto add_node = [&](int i) -> void {
		rqA[N+posA[i]] += Func{1,posA[i]};
		if(k-posL*2 <= posA[i]) sum_rqA += Func{1,posA[i]};
		rqB[N+posB[i]] += Func{1,posB[i]};
		if(posB[i] < k-posL) sum_rqB += Func{1,posB[i]};
	};
	auto rem_node = [&](int i) -> void {
		rqA[N+posA[i]] -= Func{1,posA[i]};
		if(k-posL*2 <= posA[i]) sum_rqA -= Func{1,posA[i]};
		rqB[N+posB[i]] -= Func{1,posB[i]};
		if(posB[i] < k-posL) sum_rqB -= Func{1,posB[i]};
	};
	auto increment_k = [&]() -> void {
		sum_rqA -= rqA[N+k-posL*2];
		sum_rqB += rqB[N+k-posL];
		k++;
	};
	auto increment_posL = [&]() -> void {
		rem_node(posL);
		add_node(posL + cnt);
		sum_rqA += rqA[N+k-posL*2-1];
		sum_rqA += rqA[N+k-posL*2-2];
		sum_rqB -= rqB[N+k-posL-1];
		posL++;
	};
	auto decrement_posL = [&]() -> void {
		posL--;
		sum_rqA -= rqA[N+k-posL*2-1];
		sum_rqA -= rqA[N+k-posL*2-2];
		sum_rqB += rqB[N+k-posL-1];
		add_node(posL);
		rem_node(posL + cnt);
	};

	rep(i,cnt) add_node(i);

	auto calc_score = [&]() -> long long {
		auto cA = sum_rqA;
		auto cB = sum_rqB;
		long long ans = (cA.c - cA.x * (k - posL * 2)) + (-cB.c + cB.x * (k - posL));
		return ans;
	};

	rep(kk,N-L+1){
		if(kk != 0) increment_k();
		long long score = calc_score();
		while(posL + cnt != (int)posA.size()){
			increment_posL();
			long long new_score = calc_score();
			if(score <= new_score){
				decrement_posL();
				break;
			}
			score = new_score;
		}
		cout << score << '\n';
	}
	return 0;
}


struct ios_do_not_sync{
	ios_do_not_sync(){
		std::ios::sync_with_stdio(false);
		std::cin.tie(nullptr);
	}
} ios_do_not_sync_instance;

提出情報

ジャッジ結果