fork download 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<string>
  4. #include<iostream>
  5. #include<map>
  6. using namespace std;
  7. struct Qr { int a, b, c; }Q[121212];
  8. bool sort_a(Qr a, Qr b) { return a.a < b.a; }
  9. int tr[1212121], tcnt[1212121], tn;
  10. int state[1212121];
  11. void insert_g(int w, int g) {
  12. 	tr[w + tn] = g, tcnt[w + tn] = 1;
  13. 	for (int i = (w + tn) / 2; i > 0; i /= 2) {
  14. 		tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
  15. 		tcnt[i] = 0;
  16. 		if (tr[i] == tr[i * 2])tcnt[i] += tcnt[i * 2];
  17. 		if (tr[i] == tr[i * 2 + 1])tcnt[i] += tcnt[i * 2 + 1];
  18. 	}
  19. }
  20. map<string, int>M;
  21. int main() {
  22. 	int n, m = 0, G;
  23. 	scanf("%d%d", &n, &G);
  24. 	for (int i = 0; i < n; i++) {
  25. 		int a, c; string b;
  26. 		cin >> a >> b >> c;
  27. 		if (M.find(b) == M.end())M[b] = m++;
  28. 		Q[i] = { a,M[b],c };
  29. 	}
  30. 	sort(Q, Q + n, sort_a);
  31. 	for (tn = 1; tn <= m; tn *= 2);
  32. 	for (int i = 0; i <= m; i++)state[i] = G, insert_g(i, G);
  33. 	int befmx, befcnt;
  34. 	befmx = G, befcnt = m + 1;
  35. 	int ans = 0, flag;
  36. 	for (int i = 0; i < n; i++) {
  37. 		flag = (state[Q[i].b] == befmx);
  38. 		state[Q[i].b] += Q[i].c;
  39. 		insert_g(Q[i].b, state[Q[i].b]);
  40. 		if (befmx == tr[1] && befcnt == tcnt[1])continue;
  41. 		if (flag == 1) {
  42. 			if (befmx >= tr[1]) {
  43. 				if (tr[1] != state[Q[i].b]) ans++;
  44. 				if (tr[1] == state[Q[i].b] && tcnt[1]>1) ans++;
  45. 			}
  46. 			else if (befcnt > 1) ans++;
  47. 		}
  48. 		else if (befmx < tr[1] || (befmx == tr[1] && befcnt < tcnt[1])) ans++;
  49. 		befmx = tr[1], befcnt = tcnt[1];
  50. 	}
  51. 	printf("%d", ans);
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin 
4 10
7 3 +3
4 2 -1
9 3 -1
1 1 +2
stdout 
3
https://ideone.com/bEgCwP
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!