fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. using namespace std;
  5. typedef vector<int> vi;
  6. class bit{
  7. public:
  8.     bit(int n,string strt):s(strt){ ftBuc.assign(n+2,0); }
  9. 	void adjust(int k,int v){
  10.  
  11. 	if(v=='1'&&s[k] == '1')
  12. 		return;
  13. 	else if(v=='0' && s[k] == '0')
  14. 		return;
  15. 	else if(v=='1'&&s[k] == '0')
  16. 		{ s[k] = '1';	for(;k<(int)ftBuc.size();k += leastSig1(k)) ftBuc[k]+=1; }
  17. 	else if(v=='0' && s[k] == '1' )
  18. 		{ s[k] = '0';	for(;k<(int)ftBuc.size();k += leastSig1(k)) ftBuc[k]-=1; }
  19. 	}
  20. 	int rsq(int a,int b) { return rsq(b)-(a==1?0:rsq(a-1));}
  21. 	string s;
  22. 	int rsq(int b) { int sum = 0; for(; b ; b-=leastSig1(b)) sum+=ftBuc[b]; return sum;}
  23. 	vi ftBuc;
  24. 	int leastSig1(int i) {return i&(-i);}
  25.  
  26. };
  27. int main()
  28. {
  29. 	int t;
  30. 	cin>>t;
  31. 	for(int test=1;test<=t;++test)
  32. 	{	
  33. 		int m;
  34. 		cin>>m;
  35. 		string s;
  36. 		while(m--)
  37. 		{
  38. 			int T;
  39. 			cin>>T;
  40. 			string temp;
  41. 			cin>>temp;
  42. 			while(T--)
  43. 				s.append(temp);
  44. 		}
  45. 		int n = s.size();
  46. 		bit ft(n+2,string(n+2,'0'));
  47. 		for(int i = 1;i<=n;++i)
  48. 			ft.adjust(i,s[i-1]);
  49. 		int q;
  50. 		cin>>q;
  51. 		int asks = 1;
  52. 		printf("Case %d:\n",test);
  53. 		while(q--)
  54. 		{
  55. 			char c;
  56. 			int i,j;
  57. 			cin>>c>>i>>j;
  58. 			if(c=='F')
  59. 			{
  60. 				for(int k=i+1;k<=j+1;++k)
  61. 					ft.adjust(k,'1');
  62.  
  63. 			}
  64. 			else if(c=='E')
  65. 			{
  66. 				for(int k=i+1;k<=j+1;++k)
  67. 					ft.adjust(k,'0');
  68. 			}
  69. 			else if(c == 'I')
  70. 			{
  71. 				for(int k=i+1;k<=j+1;++k)
  72. 				{
  73. 					if(ft.s[k] == '1')
  74. 						ft.adjust(k,'0');
  75. 					else
  76. 						ft.adjust(k,'1');
  77.  
  78. 				}
  79. 			}
  80. 			else if(c=='S')
  81. 				printf("Q%d: %d\n",asks++,ft.rsq(i+1,j+1));
  82.  
  83. 		}
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91. 	}		
  92.  
  93.  
  94. }
Time limit exceeded #stdin #stdout 5s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/krmc4n
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!