Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define NMAX 1000005
  3.  
  4. using namespace std;
  5.  
  6. struct A
  7. {
  8. int nr, val[10];
  9. };
  10.  
  11. bool crt ( A x, A y );
  12.  
  13. A v[NMAX];
  14. int t, n, i, j, z, nr, a[NMAX], S[NMAX], maxx, nrr;
  15. char c, s[30];
  16.  
  17. int main()
  18. {
  19. ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  20.  
  21. cin >> t;
  22. while ( t-- )
  23. {
  24. cin >> n;
  25. z = nrr = 0;
  26. for ( i = 1 ; i <= n ; i++ )
  27. {
  28. cin >> c >> nr;
  29. cin.getline ( s, 30 );
  30.  
  31. if ( nr > 0 )
  32. {
  33. v[++z].nr = nr;
  34. if ( s[1] == 'T' && c == '<' ) v[z].val[1]++;
  35. else if ( s[1] == 'T' && c == '=' ) v[z].val[3]++;
  36. else if ( s[1] == 'T' && c == '>' ) v[z].val[4]++;
  37.  
  38. else if ( s[1] == 'F' && c == '<' ) v[z].val[5]++;
  39. else if ( s[1] == 'F' && c == '=' ) v[z].val[6]++;
  40. else if ( s[1] == 'F' && c == '>' ) v[z].val[2]++;
  41. }
  42.  
  43. else
  44. {
  45. if ( s[1] == 'T' && c == '>' ) nrr++;
  46. else if ( s[1] == 'F' && c == '<' ) nrr++;
  47. else if ( s[1] == 'F' && c == '=' ) nrr++;
  48. }
  49. }
  50.  
  51. sort ( v + 1, v + n + 1, crt );
  52.  
  53. for ( j = 1 ; j < n ; j++ )
  54. {
  55. i = j + 1;
  56. while ( i <= n && v[j].nr == v[i].nr )
  57. {
  58. v[j].val[1] += v[i].val[1];
  59. v[j].val[2] += v[i].val[2];
  60. v[j].val[3] += v[i].val[3];
  61. v[j].val[4] += v[i].val[4];
  62. v[j].val[5] += v[i].val[5];
  63. v[j].val[6] += v[i].val[6];
  64.  
  65. i++;
  66. }
  67.  
  68. j = i - 1;
  69. }
  70.  
  71. for ( j = 1 ; j <= n ; j++ )
  72. {
  73. a[1] += v[j].val[1], a[j] -= v[j].val[1];
  74. a[1] += v[j].val[2], a[j+1] -= v[j].val[2];
  75. a[j] += v[j].val[3], a[j+1] -= v[j].val[3];
  76.  
  77. a[j+1] += v[j].val[4];
  78. a[j] += v[j].val[5];
  79. a[1] += v[j].val[6], a[j] -= v[j].val[6], a[j+1] += v[j].val[6];
  80.  
  81. i = j + 1;
  82. while ( i <= n && v[j].nr == v[i].nr ) i++;
  83. j = i - 1;
  84. }
  85.  
  86. S[1] = a[1];
  87. for ( i = 2 ; i <= n ; i++ ) S[i] = S[i-1] + a[i];
  88.  
  89. maxx = 0;
  90. for ( i = 1 ; i <= n ; i++ ) maxx = max ( maxx, S[i] );
  91. cout << n - maxx - nrr << '\n';
  92.  
  93. for ( i = 1 ; i <= n ; i++ )
  94. {
  95. a[i] = S[i] = v[i].nr = 0;
  96. for ( j = 1 ; j <= 6 ; j++ ) v[i].val[j] = 0;
  97. }
  98.  
  99. }
  100.  
  101. return 0;
  102. }
  103.  
  104. bool crt ( A x, A y )
  105. {
  106. if ( x.nr < y.nr ) return 1;
  107.  
  108. return 0;
  109. }
  110.  
  111. /*
  112.  
  113. 2
  114. 3
  115. = 5 True
  116. > 3 True
  117. = 1 False
  118. 2
  119. > 4 True
  120. = 4 True
  121.  
  122. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement