Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double lf;
- typedef pair<int,int> pii;
- const int oo = 1e9 + 100;
- const int MAXN = 1e5 + 100;
- const int MOD = 1e9 + 7;
- const lf EPS = 1e-9;
- int n;
- char str[MAXN];
- int open_cost, close_cost, k;
- struct data { int o, c; };
- data operator + ( const data a, const data b ) {
- int mn = min( a.o, b.c );
- return {a.o+b.o-mn, a.c+b.c-mn};
- }
- ostream& operator << ( ostream& out, const data d ) {
- out << "[data] " << d.o << ' ' << d.c;
- return out;
- }
- data st[4*MAXN];
- void build( int node = 1, int l = 1, int r = n ) {
- if( l == r ) {
- st[node] = { str[l] == '(', str[l] == ')' };
- return ;
- }
- int m = (l+r) >> 1;
- build( node+node, l, m );
- build( node+node+1, m+1, r );
- st[node] = st[node+node] + st[node+node+1];
- }
- void update( int pos, int node = 1, int l = 1, int r = n ) {
- if( l == r ) {
- st[node] = { str[pos] == '(', str[pos] == ')' };
- return ;
- }
- int m = (l+r) >> 1;
- if( pos <= m ) update( pos, node+node, l, m );
- else update( pos, node+node+1, m+1, r );
- st[node] = st[node+node] + st[node+node+1];
- }
- data query( int a, int b, int node = 1, int l = 1, int r = n ) {
- if( l == a && r == b ) return st[node];
- int m = (l+r) >> 1;
- if( b <= m ) return query( a, b, node+node, l, m );
- if( a > m ) return query( a, b, node+node+1, m+1, r );
- return query( a, m, node+node, l, m ) + query( m+1, b, node+node+1, m+1, r );
- }
- int main( ) {
- #ifdef LOCAL
- freopen( "input.txt", "r", stdin );
- // freopen( "output.txt", "w", stdout );
- #else
- #define endl '\n'
- #endif
- while( scanf( "%s", str+1 ) == 1 ) {
- n = strlen(str+1);
- int q;
- scanf( "%d %d %d %d", &q, &open_cost, &close_cost, &k );
- build();
- while( q-- ) {
- int cmd; scanf( "%d", &cmd );
- if( cmd == 1 ) {
- int pos; scanf( "%d", &pos );
- str[pos] = str[pos] == '(' ? ')' : '(';
- update(pos);
- } else {
- int a, b; scanf( "%d %d", &a, &b );
- data ans = query(a,b);
- int change_open = (ans.o/2) + (ans.o&1);
- int change_close = (ans.c/2) + (ans.c&1);
- if( (ans.o+ans.c)%2 != 0 || change_open+change_close > k ) puts( "Impossible" );
- else printf( "%d\n", change_open*open_cost + change_close*close_cost );
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement