CF3D 两层别墅
题意：给一个字符集为
先上括号序列的经典套路：( 视作 ) 视作 (，如果最小前缀和为负则无解，然后在保证可能合法（即最小前缀和非负）的情况下一个一个改成 )，如果最后整体和不为 )。
接下来是策略的正确性证明。记我们改出来的方案为 )...( 改成 (...)，改完之后每个前缀和都不减少，一定合法。
否则，
注意不能直接说「因为
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ldb;
//#define umap unordered_map
#define umap __gnu_pbds::cc_hash_table
#define mkp make_pair
#define prque priority_queue
#define emp emplace
#define empb emplace_back
#define empf emplace_front
#define invarg invalid_argument
#define cus_throw(msg) throw invarg(string(msg) + " at " + __FILE__ + ":" + to_string(__LINE__))
random_device rndv;
mt19937 rd(rndv());
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const vector<ll> millerrabin = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
const double eps = 1e-8;
inline void enter(){putchar('\n');}
inline void space(){putchar(' ');}
inline ll readll(){ll ret=0,k=1;char c;do{c=getchar();if(c=='-'){k=-1;}}while(('0'>c)|('9'<c));do{ret=(ret<<3)+(ret<<1)+c-48;c=getchar();}while(('0'<=c)&(c<='9'));return ret*k;}
inline void read(ll&x){x=readll();}
inline char readchar(){char ret;do{ret=getchar();}while(ret<=32);return ret;}
inline void read(char&x){x=readchar();}
inline string readstr(){string ret;char c;do{c=getchar();}while(c<=32);do{ret+=c;c=getchar();}while((c>32)&(c!=EOF));return ret;}
inline void read(string&x){x=readstr();}
inline void write(ll x){if(!x){putchar('0');return;}if(x<0){putchar('-');x*=-1;}char op[20]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){putchar(op[cur--]);}}
inline ostream& operator<<(ostream& out, __int128 x){if(!x){out<<"0";return out;}if(x<0){out<<"-";x*=-1;}char op[40]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){out<<op[cur--];}return out;}
// -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
namespace modint {
const ll MOD = 1;
struct modint {
ll val, mod;
void setmod(ll x) {
mod = x;
}
explicit operator ll() {
return val;
}
modint() {
val = 0, mod = MOD;
}
modint(ll v, ll m = MOD) {
if (m == 1) {
cus_throw("init modint without mod");
}
v %= m;
if (v < 0) {
v += m;
}
val = v;
mod = m;
}
};
#define chkmod(x, y) if (x.mod != y.mod) cus_throw("mod isn't the same")
modint operator+(modint x, modint y) {
chkmod(x, y);
return modint(x.val + y.val, x.mod);
}
modint operator-(modint x, modint y) {
chkmod(x, y);
return modint(x.val - y.val, x.mod);
}
modint operator*(modint x, modint y) {
chkmod(x, y);
return modint(__int128(1) * x.val * y.val, x.mod);
}
modint qpow(modint x, ll y) {
if (!y) {
return modint(1, x.mod);
} else if (y & 1) {
return x * qpow(x, y ^ 1);
} else {
return qpow(x * x, y >> 1);
}
}
modint inv(modint x) {
return qpow(x, x.mod - 2);
}
modint operator/(modint x, modint y) {
chkmod(x, y);
if (ll(y) == 0) {
cus_throw("modint divide by 0");
}
return x * inv(y);
}
modint operator+=(modint& x, modint y) {
return x = x + y;
}
modint operator-=(modint& x, modint y) {
return x = x - y;
}
modint operator*=(modint& x, modint y) {
return x = x * y;
}
modint operator/=(modint& x, modint y) {
return x = x / y;
}
bool operator==(modint x, modint y) {
chkmod(x, y);
return x.val == y.val;
}
}
const ll MAXN = 5e4 + 5;
string s;
ll lb[MAXN], rb[MAXN], n, iq[MAXN], qc;
namespace segtree {
struct sec {
ll sum = 0, mnp = inf;
explicit operator ll() {
return mnp;
}
};
sec operator+(sec x, sec y) {
sec r;
r.sum = x.sum + y.sum;
r.mnp = min(x.mnp, x.sum + y.mnp);
return r;
}
struct segtree {
ll size;
sec val[MAXN << 2];
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define mid ((lx+rx)>>1)
#define lpr l(x),lx,mid
#define rpr r(x),mid+1,rx
#define prl ll x, ll lx, ll rx
void init(ll x) {
size = 1;
while (size < x) size <<= 1;
}
void psu(ll x) {
val[x] = val[l(x)] + val[r(x)];
}
void mdf(ll p, ll v, prl) {
if (p < lx || rx < p) {
return;
}
if (p == lx && lx == rx) {
val[x].mnp = val[x].sum = v;
return;
}
mdf(p, v, lpr), mdf(p, v, rpr), psu(x);
}
void mdf(ll p, ll v) {
mdf(p, v, 1, 1, size);
}
sec qry(ll l, ll r, prl) {
if (r < lx || rx < l) {
return sec();;
}
if (l <= lx && rx <= r) {
return val[x];
}
return qry(l, r, lpr) + qry(l, r, rpr);
}
sec qry(ll l, ll r) {
return qry(l, r, 1, 1, size);
}
} st;
}
map<char, ll> cv;
ll ans = 0;
int main() {
cv['('] = cv['?'] = 1;
cv[')'] = -1;
read(s);
n = s.size();
for (ll i = 0; i < n; ++i) {
if (s[i] == '?') {
iq[++qc] = i + 1;
}
}
s = '.' + s;
for (ll i = 1; i <= qc; ++i) {
read(lb[iq[i]]), read(rb[iq[i]]);
}
segtree::st.init(n);
for (ll i = 1; i <= n; ++i) {
segtree::st.mdf(i, cv[s[i]]);
}
if (ll(segtree::st.qry(1, n)) < 0) {
puts("-1");
return 0;
}
vector<ll> a;
for (ll i = 1; i <= n; ++i) {
if (s[i] == '?') a.empb(i);
}
sort(a.begin(), a.end(), [](ll x, ll y)->bool {return mkp(rb[x] - lb[x], x) < mkp(rb[y] - lb[y], y);});
for (ll i : a) {
segtree::st.mdf(i, -1);
if (ll(segtree::st.qry(1, n)) < 0) {
segtree::st.mdf(i, 1);
s[i] = '(';
ans += lb[i];
} else {
s[i] = ')';
ans += rb[i];
}
}
ll pre = 0;
for (char c : s) {
pre += cv[c];
}
if (pre > 0) {
puts("-1");
return 0;
}
write(ans), enter(), puts(s.c_str() + 1);
return 0;
}
; ;;;;;;;; ;
; ; ; ;
; ; ; ;
; ; ; ;
; ; ;;;;;;;;;
; ; ; ;
; ; ; ;
;;;;;;;;;;; ;;;;;;;; ; ;
; ;
; ;
; ;
; ;
; ;
; ;
; ;
; ;; ;; ;
; ;; ;; ;