Advertisement
Guest User

Untitled

a guest
Mar 18th, 2013
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <vector>
  7. #include <cmath>
  8. #include <stack>
  9. #include <queue>
  10. #include <set>
  11.  
  12. using namespace std;
  13.  
  14. #define mp make_pair
  15. #define pb push_back
  16. #define x first
  17. #define y second
  18.  
  19. typedef long long ll;
  20. typedef long double ld;
  21. typedef short int si;
  22. typedef pair <int, int> pii;
  23.  
  24. const int MOD = 1e9 + 7;
  25. const int INF = 2e9 + 5;
  26. const int N = 2e5 + 5;
  27.  
  28. int n, k;
  29.  
  30. struct fenv
  31. {
  32.   int t[N];
  33.  
  34.   void add(int x, int d)
  35.   {
  36.     for (; x <= n; x = (x | (x + 1)))
  37.       t[x] += d;
  38.   }
  39.   int res(int x)
  40.   {
  41.     int sum = 0;
  42.     for (; x >= 0; x = (x & (x + 1)) - 1)
  43.       sum += t[x];
  44.     return sum;
  45.   }
  46.   int sum(int l)
  47.   {
  48.     return res(n) - res(l);
  49.   }
  50. };
  51.  
  52. int a[N], x, ans[N];
  53. fenv b, c;
  54.  
  55. int main()
  56. {
  57.   freopen("battle.in", "r", stdin);
  58.   freopen("battle.out", "w", stdout);
  59.  
  60.   cin >> n >> k;
  61.   for (int i = 0; i < n; i++)
  62.   {
  63.     scanf("%d", &x);
  64.     x--;
  65.     a[x] = b.sum(x);
  66.     b.add(x, 1);
  67.   }
  68.  
  69.   for (int i = 0; i < n; i++)
  70.     a[i] = max(0, a[i] - k);
  71.  
  72.   for (int i = 0; i < n; i++)
  73.   {
  74.     int l = 0, r = n, m;
  75.     while (l + 1 < r)
  76.     {
  77.       m = (l + r) / 2;
  78.       if (m - (m ? c.res(m - 1) : 0) > a[i]) r = m;
  79.       else l = m;
  80.     }
  81.     c.add(l, 1);
  82.     ans[l] = i;
  83.   }
  84.  
  85.   for (int i = 0; i < n; i++)
  86.     cout << ans[i] + 1 << " ";
  87.  
  88.   return 0;
  89. }
  90.  
  91. /*
  92. 5859589000
  93. 17053987120
  94. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement