fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <cassert>
  4. #include <cstdio>
  5. using namespace std;
  6. typedef vector<int> vi;
  7. struct RangeResult{ int maxi, sn, waste; };
  8. RangeResult merge(const RangeResult& a, const RangeResult& b){
  9.     return { max(a.maxi, b.maxi), a.sn + b.sn, a.waste + b.waste };
  10. }
  11. struct snode {
  12.     int i, j; RangeResult res;
  13.     snode *l, *r;
  14.     ~snode() { delete l; delete r; }
  15.     snode(int i, int j, int v ): i(i), j(j), res({v,0,0}) {
  16.         if (j - i == 1) {
  17.             l = r = NULL;
  18.         } else {
  19.             int k = i + j >> 1;
  20.             l = new snode(i, k, v);
  21.             r = new snode(k, j, v);
  22.         }
  23.     }
  24.     void update(int v){
  25.     	if( j - i == 1 ){
  26.     		res.maxi -= v; assert(res.maxi>=0);
  27.     		res.sn = 1; res.waste = res.maxi;
  28.     	}else{
  29.     		if( l->res.maxi >= v ) l->update(v);
  30.     		else r->update(v);
  31.     		res = merge( l->res, r->res );
  32.     	}
  33.     }
  34. };
  35. struct segment {
  36.     snode *root;
  37.     segment() : root(0) {}
  38.     void init(int n, int v) {
  39.         if(root) delete root;
  40.         root = new snode(0, n, v);
  41.     }
  42.     void update(int v){
  43.     	root->update(v);
  44.     }
  45. };
  46.  
  47. const int MAXS=1e5+10;
  48. int T, K,N, a,b; char buf[128];
  49. segment tree;
  50. int main() {
  51. 	scanf("%d",&T);
  52. 	while(T--){
  53. 		scanf("%d%d\n",&K,&N);
  54. 		tree.init(MAXS, K);
  55. 		for(int i=0;i<N;i++){
  56. 			fgets(buf, 128, stdin);
  57. 			if(buf[0]=='b'){
  58. 				sscanf(buf, "b %d %d",&a,&b);
  59. 				for(int j=0;j<a;j++)
  60. 					tree.update(b);
  61. 				i+=(a-1);
  62. 			}else{
  63. 				sscanf(buf, "%d",&a);
  64. 				tree.update(a);
  65. 			}
  66. 		} auto& ret = tree.root->res;
  67. 		printf("%d %d\n",ret.sn,ret.waste);
  68. 	}
  69. 	return 0;
  70. }
Success #stdin #stdout 0.03s 9456KB
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/ScQcj5
http://w...content-available-to-author-only...j.com/problems/HELPR2D2/
language:
C++14 (gcc 8.3)
created:
10 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!