Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.10 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. cin >> t;
  20. while ( t-- )
  21. {
  22. cin >> n;
  23. z = nrr = 0;
  24. for ( i = 1 ; i <= n ; i++ )
  25. {
  26. cin >> c >> nr;
  27. cin.getline ( s, 30 );
  28.  
  29. if ( nr > 0 )
  30. {
  31. v[++z].nr = nr;
  32. if ( s[1] == 'T' && c == '<' ) v[z].val[1]++;
  33. else if ( s[1] == 'T' && c == '=' ) v[z].val[3]++;
  34. else if ( s[1] == 'T' && c == '>' ) v[z].val[4]++;
  35.  
  36. else if ( s[1] == 'F' && c == '<' ) v[z].val[5]++;
  37. else if ( s[1] == 'F' && c == '=' ) v[z].val[6]++;
  38. else if ( s[1] == 'F' && c == '>' ) v[z].val[2]++;
  39. }
  40.  
  41. else
  42. {
  43. if ( s[1] == 'T' && c == '>' ) nrr++;
  44. else if ( s[1] == 'F' && c == '<' ) nrr++;
  45. else if ( s[1] == 'F' && c == '=' ) nrr++;
  46. }
  47. }
  48.  
  49. sort ( v + 1, v + n + 1, crt );
  50.  
  51. for ( j = 1 ; j < n ; j++ )
  52. {
  53. i = j + 1;
  54. while ( i <= n && v[j].nr == v[i].nr )
  55. {
  56. if ( v[i].val[1] != 0 ) v[j].val[1] += v[i].val[1];
  57. if ( v[i].val[2] != 0 ) v[j].val[2] += v[i].val[2];
  58. if ( v[i].val[3] != 0 ) v[j].val[3] += v[i].val[3];
  59. if ( v[i].val[4] != 0 ) v[j].val[4] += v[i].val[4];
  60. if ( v[i].val[5] != 0 ) v[j].val[5] += v[i].val[5];
  61. if ( v[i].val[6] != 0 ) v[j].val[6] += v[i].val[6];
  62.  
  63. i++;
  64. }
  65.  
  66. j = i - 1;
  67. }
  68.  
  69. for ( j = 1 ; j <= n ; j++ )
  70. {
  71. if ( v[j].val[1] != 0 ) a[1] += v[j].val[1], a[j] -= v[j].val[1];
  72. if ( v[j].val[2] != 0 ) a[2] += v[j].val[2], a[j+1] -= v[j].val[2];
  73. if ( v[j].val[3] != 0 ) a[j] += v[j].val[3], a[j+1] -= v[j].val[3];
  74. if ( v[j].val[4] != 0 ) a[j+1] += v[j].val[4];
  75. if ( v[j].val[5] != 0 ) a[j] += v[j].val[5];
  76. if ( v[j].val[6] != 0 ) a[1] += v[j].val[6], a[j] -= v[j].val[6], a[j+1] += v[j].val[6];
  77.  
  78. i = j + 1;
  79. while ( i <= n && v[j].nr == v[i].nr ) i++;
  80. j = i - 1;
  81. }
  82.  
  83. S[1] = a[1];
  84. for ( i = 2 ; i <= n ; i++ ) S[i] = S[i-1] + a[i];
  85.  
  86. maxx = 0;
  87. for ( i = 1 ; i <= n ; i++ ) maxx = max ( maxx, S[i] );
  88. cout << n - maxx - nrr << '\n';
  89.  
  90. /*for ( i = 1 ; i <= n ; i++ ) cout << S[i] << ' ';
  91. cout << '\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