fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <string>
  8. #include <climits>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <sstream>
  12. using namespace  std;
  13.  
  14. #define MOD 1000000007
  15. #define pb push_back
  16. #define mp make_pair
  17. #define F first
  18. #define S second
  19. #define N 100005
  20. #define PII pair<int,int>
  21.  
  22. int a[N];
  23. int b[4*N];
  24.  
  25. void update(int n, int start, int end, int value)
  26. {
  27. 	if(value>b[n]) return;
  28. 	if(start==end) {b[n]-=value; a[start]=b[n]; return;}
  29. 	else
  30. 	{
  31. 		int mid = (start+end)/2;
  32. 		if(b[2*n]>=value) update(2*n,start,mid,value);
  33. 		else update(2*n+1,mid+1,end,value);
  34. 		b[n] = max(b[2*n],b[2*n+1]);
  35. 	}
  36. }
  37.  
  38. void build(int n, int start, int end ,int k)
  39. {
  40. 	if(start==end) { a[start]=b[n]=k;  return;}
  41. 	int mid = (start+end)/2;
  42. 	build(2*n,start,mid,k);
  43. 	build(2*n+1,mid+1,end,k);
  44. 	b[n] = k;
  45. }
  46.  
  47.  
  48. int main()
  49. {
  50. 	ios_base::sync_with_stdio(0);
  51. 	cin.tie(0);
  52.  
  53. 	#ifndef ONLINE_JUDGE
  54. 	freopen("inp.txt","r",stdin);
  55. 	freopen("out.txt","w",stdout);
  56. 	#endif
  57.  
  58. 	int t,k,n,i,R,V;
  59. 	string s;
  60.  
  61. 	cin>>t;
  62. 	while(t--)
  63. 	{
  64. 		cin>>k>>n;
  65. 		build(1,0,n-1,k);
  66.  
  67. 		int count=0;
  68. 		while(count<n)
  69. 		{
  70.  
  71. 			cin>>s;
  72. 			int l=s.size();
  73.  
  74. 			if(s[0]=='b') 
  75. 			{
  76. 				cin>>R>>V;
  77. 				for(int i=1;i<=R;i++) update(1,0,n-1,V);
  78. 				count+=R;	
  79. 			}	
  80. 			else 
  81. 			{
  82. 				i=0;V=0;
  83. 				while(i<l) { V=V*10+(s[i]-'0'); i++;}
  84. 				update(1,0,n-1,V); 
  85. 				count++;
  86. 			}
  87. 		}
  88.  
  89. 		long long sum=0;
  90.  
  91. 		for(i=0;i<n;i++)
  92. 		{
  93. 			if(a[i]!=k) sum+=a[i];
  94. 			else break;
  95. 		}
  96. 		cout<<i<<" "<<sum<<"\n";	
  97. 	}
  98.  
  99.  
  100. 	return 0;
  101. }
Success #stdin #stdout 0s 16400KB
comments (?)
stdin
copy 
2
100
3
50
25
70
100
4
50
b 2 40
20
stdout
copy 
2 55
2 50
https://ideone.com/FPt6ZD
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!