Advertisement
Guest User

Untitled

a guest
Oct 10th, 2018
332
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double lf;
  7. typedef pair<int,int> pii;
  8.  
  9. const int oo = 1e9 + 100;
  10. const int MAXN = 1e5 + 100;
  11. const int MOD = 1e9 + 7;
  12. const lf EPS = 1e-9;
  13.  
  14. int n;
  15. char str[MAXN];
  16. int open_cost, close_cost, k;
  17.  
  18. struct data { int o, c; };
  19. data operator + ( const data a, const data b ) {
  20.   int mn = min( a.o, b.c );
  21.   return {a.o+b.o-mn, a.c+b.c-mn};
  22. }
  23. ostream& operator << ( ostream& out, const data d ) {
  24.   out << "[data] " << d.o << ' ' << d.c;
  25.   return out;
  26. }
  27.  
  28. data st[4*MAXN];
  29.  
  30. void build( int node = 1, int l = 1, int r = n ) {
  31.   if( l == r ) {
  32.     st[node] = { str[l] == '(', str[l] == ')' };
  33.     return ;
  34.   }
  35.   int m = (l+r) >> 1;
  36.   build( node+node, l, m );
  37.   build( node+node+1, m+1, r );
  38.   st[node] = st[node+node] + st[node+node+1];
  39. }
  40.  
  41. void update( int pos, int node = 1, int l = 1, int r = n ) {
  42.   if( l == r ) {
  43.     st[node] = { str[pos] == '(', str[pos] == ')' };
  44.     return ;
  45.   }
  46.   int m = (l+r) >> 1;
  47.   if( pos <= m ) update( pos, node+node, l, m );
  48.   else update( pos, node+node+1, m+1, r );
  49.   st[node] = st[node+node] + st[node+node+1];
  50. }
  51.  
  52. data query( int a, int b, int node = 1, int l = 1, int r = n ) {
  53.   if( l == a && r == b ) return st[node];
  54.   int m = (l+r) >> 1;
  55.   if( b <= m ) return query( a, b, node+node, l, m );
  56.   if( a > m ) return query( a, b, node+node+1, m+1, r );
  57.   return query( a, m, node+node, l, m ) + query( m+1, b, node+node+1, m+1, r );
  58. }
  59.  
  60. int main( ) {
  61.  
  62.   #ifdef LOCAL
  63.     freopen( "input.txt", "r", stdin );
  64.     // freopen( "output.txt", "w", stdout );
  65.   #else
  66.     #define endl '\n'
  67.   #endif
  68.  
  69.   while( scanf( "%s", str+1 ) == 1 ) {
  70.     n = strlen(str+1);
  71.     int q;
  72.     scanf( "%d %d %d %d", &q, &open_cost, &close_cost, &k );
  73.     build();
  74.     while( q-- ) {
  75.       int cmd; scanf( "%d", &cmd );
  76.       if( cmd == 1 ) {
  77.         int pos; scanf( "%d", &pos );
  78.         str[pos] = str[pos] == '(' ? ')' : '(';
  79.         update(pos);
  80.       } else {
  81.         int a, b; scanf( "%d %d", &a, &b );
  82.         data ans = query(a,b);
  83.         int change_open = (ans.o/2) + (ans.o&1);
  84.         int change_close = (ans.c/2) + (ans.c&1);
  85.         if( (ans.o+ans.c)%2 != 0 || change_open+change_close > k ) puts( "Impossible" );
  86.         else printf( "%d\n", change_open*open_cost + change_close*close_cost );
  87.       }
  88.     }
  89.   }
  90.  
  91.   return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement