Advertisement
Guest User

Untitled

a guest
Mar 5th, 2015
320
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. typedef long long int lld;
  2.  
  3. lld E[10010];
  4. lld ST[65536];
  5.  
  6. lld init( int root, int beg, int end, bool flag ){
  7. if( beg == end ) return ST[root] = E[beg];
  8.  
  9. int mid = ( beg + end ) / 2;
  10. int l = 2 * root + 1;
  11. int r = 2 * root + 2;
  12.  
  13. lld sum = 0;
  14. if( flag )
  15. sum = init(l,beg,mid,false) - init(r,mid+1,end,false);
  16.  
  17. else
  18. sum = ST[root] = init(l,beg,mid,true) + init(r,mid+1,end,true);
  19.  
  20. return ST[root] = sum;
  21. }
  22.  
  23. void update( int root, int beg, int end, int p, lld diff, bool flag ){
  24. if( beg >= end || p < beg || p > end ) return;
  25.  
  26. int length = end - beg + 1;
  27.  
  28. int mid = ( beg + end ) / 2;
  29. int l = 2 * root + 1;
  30. int r = 2 * root + 2;
  31.  
  32. if( flag ){
  33. if( length % 2 == 0 || root < end ) ST[root] += diff;
  34. update(l,beg,mid,p,diff,false);
  35. update(r,mid+1,end,p,diff,false);
  36. }
  37. else{
  38. if( length % 2 == 0 || root < end ) ST[root] -= diff;
  39. update(l,beg,mid,p,diff,true);
  40. update(r,mid+1,end,p,diff,true);
  41. }
  42. }
  43.  
  44. void ans( int t ){
  45. if( ST[0] % 2 ){
  46. printf("%lld %s\n", ST[0], ( t % 2 ) ? "Rusa" : "Sanches");
  47. }
  48. else{
  49. printf("%lld %s\n", ST[0], ( t % 2 ) ? "Sanches" : "Rusa");
  50. }
  51. }
  52.  
  53. int main(){
  54.  
  55. int T, n, q;
  56.  
  57. scanf("%d", &T );
  58.  
  59. for( int t = 1; t <= T; t++ ){
  60. scanf("%d %d", &n, &q );
  61.  
  62. for( int i = 0; i < n; i++ ) scanf("%lld", &E[i] );
  63.  
  64. init(0,0,n-1,n%2);
  65.  
  66. ans(t);
  67.  
  68. lld v,p;
  69. while( q-- ){
  70. scanf(" %lld %lld", &p, &v );
  71.  
  72. update(0,0,n-1,p-1,E[p-1]-v,n%2);
  73.  
  74. ans(t);
  75. }
  76. }
  77.  
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement