Advertisement
Guest User

Untitled

a guest
Jan 25th, 2015
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.57 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<cstring>
  5. #include<queue>
  6. #include<map>
  7. #include<set>
  8. #include<algorithm>
  9. #include<stack>
  10. #include<cmath>
  11. #include<iomanip>
  12. #include<cstdlib>
  13. #include<sstream>
  14. #include<climits>
  15. using namespace std;
  16. #define f(i,a,b) for(i=a;i<b;i++)
  17. #define rep(i,n) f(i,0,n)
  18. #define pb push_back
  19. #define ss second
  20. #define ff first
  21. #define vi vector<int>
  22. #define vl vector<ll>
  23. #define s(n) scanf("%d",&n)
  24. #define ll long long
  25. #define mp make_pair
  26. #define PII pair <int ,int >
  27. #define PLL pair<ll,ll>
  28. #define inf 1000*1000*1000+5
  29. #define v(a,size,value) vi a(size,value)
  30. #define sz(a) a.size()
  31. #define all(a) a.begin(),a.end()
  32. #define tri pair < int , PII >
  33. #define TRI(a,b,c) mp(a,mp(b,c))
  34. #define xx ff
  35. #define yy ss.ff
  36. #define zz ss.ss
  37. #define in(n) n = inp()
  38. #define vii vector < PII >
  39. #define vll vector< PLL >
  40. #define viii vector < tri >
  41. #define vs vector<string>
  42. #define DREP(a) sort(all(a)); a.erase(unique(all(a)),a.end());
  43. #define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
  44. #define ok if(debug)
  45. #define trace1(x) ok cerr << #x << ": " << x << endl;
  46. #define trace2(x, y) ok cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  47. #define trace3(x, y, z) ok cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  48. #define trace4(a, b, c, d) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
  49. << #d << ": " << d << endl;
  50. #define trace5(a, b, c, d, e) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
  51. << #d << ": " << d << " | " << #e << ": " << e << endl;
  52. #define trace6(a, b, c, d, e, f) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
  53. << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  54. ll MOD = int(1e9) + 7;
  55. #define gc getchar()
  56. inline int inp(){register int n=0,s=1,c=gc;if(c=='-')s=-1;while(c<48)c=gc;while(c>47)n=(n<<3)+(n<<1)+c-'0',c = gc;return n*s;}
  57. #define pc(x) putchar(x) //_unlocked(x);
  58. inline void writeInt (ll n)
  59. {ll N = n, rev, count = 0;rev = N; if (N == 0) { pc('0'); pc('\n'); return ;}
  60. while ((rev % 10) == 0) { count++; rev /= 10;}rev = 0; while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
  61. while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}while (count--) pc('0'); }
  62. const int N = 1000*100+5;
  63. int debug = 1;
  64.  
  65. int a[N],b[N],c[N];
  66. int main()
  67. {
  68. // ios::sync_with_stdio(false);
  69. int i,j,t;
  70. // cin>>t;
  71. s(t);
  72. while(t--)
  73. {
  74. memset(a,0,sizeof(a));
  75. memset(b,0,sizeof(b));
  76. memset(c,0,sizeof(c));
  77. int p,q,r;
  78. s(p);
  79. rep(i,p)
  80. s(a[i+1]);
  81. s(q);
  82. rep(i,q)
  83. s(b[i+1]);
  84. s(r);
  85. rep(i,r)
  86. s(c[i+1]);
  87. ll ans = 0;
  88.  
  89. for( i = 1; i <= q; i++)
  90. {
  91. int num = b[i];
  92. ll L = 0 , R = r + 1;
  93. // L = upper_bound(a+1,a+p+1,num) - a - 1;
  94. int lo = 1, hi = p;
  95. while(lo <= hi)
  96. {
  97. int mid = (lo + hi) >> 1;
  98. if( a[mid] <= num)
  99. {
  100. L = mid;
  101. lo = mid + 1;
  102. }
  103. else
  104. hi = mid - 1;
  105. }
  106. // R = lower_bound(c+1,c+r+1,num) - c;
  107.  
  108. lo = 1;hi = r;
  109. while(lo <= hi)
  110. {
  111. int mid = (lo + hi) >> 1;
  112. if(c[mid] >= num)
  113. {
  114. hi = mid - 1;
  115. R = mid;
  116. }
  117. else
  118. lo = mid + 1;
  119. }
  120. L = min(L,(ll)i);
  121. R = max(R,(ll)i);
  122.  
  123. ans += max((ll)0,L*((ll)r + 1 - R));
  124. // trace1(ans);
  125. }
  126. printf("%lld\n",ans);
  127. // cout<<ans<<endl;
  128. }
  129. cin>>i;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement