Advertisement
konchin_shih

a139

Feb 28th, 2021
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include<iostream>
  2. #include<fstream>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<numeric>
  6. #define endl '\n'
  7. using namespace std;
  8.  
  9. //#define _FILE
  10.  
  11. struct BIT {
  12.     size_t size;
  13.     vector<int> data;
  14.     inline void update(int i, int x = 1) {
  15.         auto lowbit = [](int a) {return a & -a;};
  16.         while (i <= int(size)) {
  17.             data[i] += x;
  18.             i += lowbit(i);
  19.         }
  20.     }
  21.     inline int operator[](int i) {
  22.         int res = 0;
  23.         auto lowbit = [](int a) {return a & -a;};
  24.         while (i > 0) {
  25.             res += data[i];
  26.             i -= lowbit(i);
  27.         }
  28.         return res;
  29.     }
  30.     BIT(size_t x): size(x), data(size + 1, 0) {}
  31. };
  32.  
  33. void solve() {
  34.     int n;
  35.     while (cin >> n, n) {
  36.         vector<pair<int, int>> v(n);
  37.         vector<int> ans(n), st(n), ori(n);
  38.         for (auto& i : v)
  39.             cin >> i.first >> i.second;
  40.         iota(ori.begin(), ori.end(), 0);
  41.         iota(st.begin(), st.end(), 0);
  42.         sort(ori.begin(), ori.end(), [&](auto a, auto b) {return v[a].first < v[b].first || (v[a].first == v[b].first && v[a].second > v[b].second);});
  43.         for_each(st.begin(), st.end(), [&](auto & a) {a = v[a].second;});
  44.         sort(st.begin(), st.end());
  45.         st.resize(unique(st.begin(), st.end()) - st.begin());
  46.         for (auto& i : v)
  47.             i.second = st.size() - (lower_bound(st.begin(), st.end(), i.second) - st.begin());
  48.         BIT b(n);
  49.         for (int k = n - 1; k >= 0; k--) {
  50.             int i = ori[k];
  51.             ans[i] = b[v[i].second - 1];
  52.             b.update(v[i].second);
  53.         }
  54.         for (const auto& i : ans)
  55.             cout << i << endl;
  56.     }
  57. }
  58.  
  59. int main() {
  60.     cin.tie(nullptr);
  61.     cout.tie(nullptr);
  62.     ios::sync_with_stdio(false);
  63. //
  64. #ifdef _FILE
  65.     fstream fin(  "in.txt", ios::in);
  66.     fstream fout("out.txt", ios::out | ios::trunc);
  67.     cin.rdbuf(fin.rdbuf());
  68.     cout.rdbuf(fout.rdbuf());
  69. #endif
  70. //
  71.     solve();
  72. //
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement