Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define mp make_pair
  6. #define ff first
  7. #define ss second
  8. #define xd puts("XD")
  9. #define endl puts("")
  10. #define ub upper_bound
  11. #define lb lower_bound
  12. #define mn 200010
  13.  
  14. int n,m,wsk,a,r;
  15. int stan[mn], ile[mn];
  16. int zam[1000010];
  17. int tree[2097300];
  18.  
  19. void test_zam()
  20. {
  21. for (int i=1; i<=10; i++)
  22. {
  23. printf ("i=%d zam[i]=%d\n", i, zam[i]);
  24. }
  25. }
  26. void inserd(int x, int pp, int pk, int zp, int zk)
  27. {
  28. if (pk<zp || zk<pp)
  29. {
  30. return;
  31. }
  32. if (zp<=pp && pk<=zk)
  33. {
  34. tree[x]++;
  35. return;
  36. }
  37. int sr=(pp+pk)/2;
  38. inserd(2*x, pp, sr, zp, zk);
  39. inserd(2*x+1, sr+1, pk, zp, zk);
  40. }
  41. int main()
  42. {
  43. scanf ("%d%d", &n, &m);
  44. r=1;
  45. while (r<1000000)
  46. {
  47. r*=2;
  48. }
  49. for (int i=1; i<=n; i++)
  50. {
  51. scanf ("%d", &stan[i]);
  52. stan[i]*=-1;
  53. }
  54. //xd;
  55. for (int i=1; i<=m; i++)
  56. {
  57. scanf ("%d", &a);
  58. inserd (1, 1, r, 1, a);
  59. }
  60. for (int i=r; i-r+1<=1000000; i++)
  61. {
  62. int x=i;
  63. while (x>0)
  64. {
  65. zam[i-r+1]+=tree[x];
  66. ile[i-r+1]+=tree[x];
  67. x/=2;
  68. }
  69. }
  70. sort (stan+1, stan+1+n);
  71. for (int i=1; i<=n; i++)
  72. {
  73. stan[i]*=-1;
  74. }
  75. //test_zam();
  76. wsk=1;
  77. for (int i=1; i<=1000000; i++)
  78. {
  79. //printf ("i=%d zam[i]=%d ile[i]=%d\n", i, zam[i], ile[i]);
  80. while (stan[wsk]<zam[i])
  81. {
  82. //printf ("PETLA wsk=%d stan[wsk]=%d\n", wsk, stan[wsk]);
  83. zam[i]-=stan[wsk];
  84. wsk++;
  85. //printf ("zam[i]=%d wsk=%d\n", zam[i], wsk);
  86. if (wsk>n)
  87. {
  88. puts ("NIE");
  89. return 0;
  90. }
  91. }
  92. stan[wsk]-=zam[i];
  93. stan[wsk]=min(stan[wsk], ile[i]-zam[i]);
  94. //printf ("wsk=%d stan[wsk]=%d\n", wsk, stan[wsk]);
  95. }
  96. puts ("TAK");
  97. return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement