結果
問題 | No.3144 Parentheses Modification and Rotation (01 Ver.) |
ユーザー |
![]() |
提出日時 | 2025-05-16 22:23:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 8,895 bytes |
コンパイル時間 | 2,581 ms |
コンパイル使用メモリ | 210,936 KB |
実行使用メモリ | 7,552 KB |
最終ジャッジ日時 | 2025-05-16 22:23:07 |
合計ジャッジ時間 | 5,055 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#pragma region /* \(^o^)/ import sys 私は人間です. 吾輩はやれば出来る子である. ∩ ∩ (´・ω・) _| ⊃/(___ / └-(____/  ̄ ̄ ̄ ̄ ̄ ̄ ̄ やる気はまだない. ⊂⌒/ヽ-、__ /⊂_/____ /  ̄ ̄ ̄ ̄ ̄ ̄ ̄ */ #include<algorithm> #include<array> #include<bitset> #include<cassert> #include<chrono> #include<cinttypes> #include<climits> #include<cmath> #include<complex> #include<cstdio> #include<cstring> #include<deque> #include<functional> #include<iomanip> #include<iostream> #include<iterator> #include<limits> #include<map> #include<numeric> #include<queue> #include<random> #include<set> #include<sstream> #include<stack> #include<string> #include<tuple> #include<type_traits> #include<unordered_map> #include<unordered_set> #include<utility> #include<vector> using namespace std; struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}}init; using ll = long long; using ull = unsigned long long; using ld = long double; #define all(x) begin((x)), end((x)) #define pb push_back #define mp make_pair #define mt make_tuple #define uq(v) v.erase(unique(begin(v), end(v)), end(v)) #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _rep1(n) for(int i=0;i<n;++i) #define _rep2(i,n) for(int i=0;i<n;++i) #define _rep3(i,a,b) for(int i=a;i<b;++i) #define _rep4(i,a,b,c) for(int i=a;i<b;i+=c) #define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__) #define _rrep1(n) for(int i=(n)-1;i>=0;i--) #define _rrep2(i,n) for(int i=(n)-1;i>=0;i--) #define _rrep3(i,a,b) for(int i=(b)-1;i>=(a);i--) #define _rrep4(i,a,b,c) for(int i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__) template<class T> using pq = priority_queue<T>; template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>; template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;} template<class T> bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;} template<class T> auto min(const T& a){ return *min_element(all(a)); } template<class T> auto max(const T& a){ return *max_element(all(a)); } constexpr ull INF = (1ULL << 61) + (1ULL << 30); constexpr int inf = (1 << 30); constexpr ld EPS = 1e-9; constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1 ,0, -1, 1, -1, 1, -1}; #pragma endregion template<typename S2, typename Op, typename E, typename F2, typename Mapping, typename Composition, typename Id> struct LambdaActedMonoid{ using S = S2; using F = F2; S op(const S &a, const S &b) const {return _op(a, b);} S e() const {return _e();} S mapping(const S &x, const F &f) const {return _mapping(x, f);} F composition(const F &f, const F &g) const {return _composition(f, g);} F id() const {return _id();} LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition,Id _id): _op(_op), _e(_e), _mapping(_mapping), _composition(_composition), _id(_id){} private: Op _op; E _e; Mapping _mapping; Composition _composition; Id _id; }; template<typename Op, typename E, typename Mapping, typename Composition, typename Id> LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition, Id _id) -> LambdaActedMonoid<decltype(_e()), Op, E, decltype(_id()), Mapping, Composition, Id>; template<typename ActedMonoid> struct LazySegmentTree{ using S = typename ActedMonoid::S; using F = typename ActedMonoid::F; private: ActedMonoid m; int n{}, sz{}, height{}; vector<S> dat; vector<F> lazy; inline void update(int k){ dat[k] = m.op(dat[2 * k + 0], dat[2 * k + 1]); } inline void all_apply(int k, const F &x){ dat[k] = m.mapping(dat[k], x); if(k < sz) lazy[k] = m.composition(lazy[k], x); } inline void propagate(int k){ if(lazy[k] != m.id()){ all_apply(2 * k + 0, lazy[k]); all_apply(2 * k + 1, lazy[k]); lazy[k] = m.id(); } } public: LazySegmentTree() = default; explicit LazySegmentTree(ActedMonoid m, int n): m(m), n(n){ sz = 1; height = 0; while(sz < n) sz <<= 1, ++height; dat.assign(2 * sz, m.e()); lazy.assign(2 * sz, m.id()); } explicit LazySegmentTree(ActedMonoid m, const vector<S> &v): LazySegmentTree(m, v.size()){ build(v); } void build(const vector<S> &v){ assert(n == (int)v.size()); for(int k = 0; k < n; ++k) dat[k + sz] = v[k]; for(int k = sz - 1; k > 0; --k) update(k); } void set(int k, const S &x){ k += sz; for(int i = height; i > 0; --i) propagate(k >> i); dat[k] = x; for(int i = 1; i <= height; ++i) update(k >> i); } S get(int k){ k += sz; for(int i = height; i > 0; --i) propagate(k >> i); return dat[k]; } S operator[](int k){return get(k);} S query(int l, int r){ if(l >= r) return m.e(); l += sz; r += sz; for(int i = height; i > 0; --i){ if(((l >> i) << i) != l) propagate(l >> i); if(((r >> i) << i) != r) propagate((r - 1) >> i); } S L = m.e(), R = m.e(); for(; l < r; l >>= 1, r >>= 1){ if(l & 1) L = m.op(L, dat[l++]); if(r & 1) R = m.op(dat[--r], R); } return m.op(L, R); } S all_query() const {return dat[1];} void apply(int k, const F &f){ k += sz; for(int i = height; i > 0; --i) propagate(k >> i); dat[k] = m.mapping(dat[k], f); for(int i = 1; i <= height; ++i) update(k >> i); } void apply(int l, int r, const F &f){ if(l >= r) return; l += sz; r += sz; for(int i = height; i > 0; --i){ if(((l >> i) << i) != l) propagate(l >> i); if(((r >> i) << i) != r) propagate((r - 1) >> i); } int l2 = l, r2 = r; for(; l < r; l >>= 1, r >>= 1){ if(l & 1) all_apply(l++, f); if(r & 1) all_apply(--r, f); } l = l2, r = r2; for(int i = 1; i <= height; ++i){ if(((l >> i) << i) != l) update(l >> i); if(((r >> i) << i) != r) update((r - 1) >> i); } } template<typename C> int find_first(int l, const C &check){ if(l >= n) return n; l += sz; for(int i = height; i > 0; --i) propagate(l >> i); S sum = m.e(); do{ while((l & 1) == 0) l >>= 1; if(check(m.op(sum, dat[l]))){ while(l < sz){ propagate(l); l <<= 1; auto nxt = m.op(sum, dat[l]); if(not check(nxt)){ sum = nxt; ++l; } } return l + 1 - sz; } sum = m.op(sum, dat[l++]); }while((l & -l) != l); return n; } template<typename C> int find_last(int r, const C &check){ if(r <= 0) return -1; r += sz; for(int i = height; i > 0; --i) propagate((r - 1) >> i); S sum = m.e(); do{ --r; while(r > 1 && (r & 1)) r >>= 1; if(check(m.op(dat[r], sum))){ while(r < sz){ propagate(r); r = (r << 1) + 1; auto nxt = m.op(dat[r], sum); if(not check(nxt)){ sum = nxt; --r; } } return r - sz; } sum = m.op(dat[r], sum); }while((r & -r) != r); return -1; } }; auto op1 = [](int a, int b){return min(a, b); }; auto e1 = []() { return 0; }; auto mapping1 = [](int x, int f){return x + f;}; auto composition1 = [](int f, int g){return f + g;}; auto id1 = [](){return 0;}; int main(){ int N; cin >> N; string S; cin >> S; int R, M; cin >> R >> M; if(N & 1){ cout << "-1\n"; return 0; } int ans = inf; LazySegmentTree seg(LambdaActedMonoid(op1, e1, mapping1, composition1, id1), 2 * N); int cutkari = 0; rep(i, N){ if(S[i] == '(') ++cutkari; else --cutkari; seg.set(N + i, cutkari); } int cur1 = max((-seg.query(N, N * 2) + 1) / 2, 0); ans = cur1 + (seg[2 * N - 1] + cur1 * 2) / 2; rep(i, 1, N){ seg.apply(N - i, 2 * N - i, (S[N - i] == '(' ? 1 : -1)); int cur = max((-seg.query(N - i, N * 2 - i) + 1) / 2, 0); ans = min(ans, cur + (seg[2 * N - 1] + cur * 2) / 2); } cout << ans << "\n"; }