fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i,a,b) for (auto i=(a); i<=(b); ++i)
  8. #define nl "\n"
  9.  
  10. using ll = long long;
  11.  
  12. const int mod = 1e9+7;
  13.  
  14. inline void rf(){
  15.     ios::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.     if (fopen(file".inp","r")){
  18.         freopen(file".inp","r",stdin);
  19.         freopen(file".out","w",stdout);
  20.     }
  21. }
  22.  
  23. int n, q;
  24. map<int, long long> cnt;  
  25.  
  26. inline bool dec_one(map<int, long long> &mp, int x){
  27.     auto it = mp.find(x);
  28.     if (it == mp.end() || it->second == 0) return false;
  29.     if (--(it->second) == 0) mp.erase(it);
  30.     return true;
  31. }
  32.  
  33. inline bool merge_ab(map<int, long long> &mp, int a, int b){
  34.     if (a == b){
  35.         auto it = mp.find(a);
  36.         if (it == mp.end() || it->second < 2) return false;
  37.         it->second -= 2;
  38.         if (it->second == 0) mp.erase(it);
  39.         ++mp[a+b];
  40.         return true;
  41.     } else {
  42.         auto ita = mp.find(a), itb = mp.find(b);
  43.         if (ita == mp.end() || ita->second == 0) return false;
  44.         if (itb == mp.end() || itb->second == 0) return false;
  45.         // an toàn vì a != b
  46.         if (--(ita->second) == 0) mp.erase(ita);
  47.         if (--(itb->second) == 0) mp.erase(itb);
  48.         ++mp[a+b];
  49.         return true;
  50.     }
  51. }
  52.  
  53. static inline long long count_pairs_leq(const vector<int> &val, const vector<long long> &c, int x){
  54.     const int m = (int)val.size();
  55.     long long ans = 0;
  56.     int j = 0;
  57.     long long window = 0; 
  58.  
  59.     for (int i = 0; i < m; ++i){
  60.         if (j < i){ j = i; window = 0; }
  61.         if (window == 0) window += c[j];
  62.  
  63.         while (j+1 < m && val[j+1] - val[i] <= x){
  64.             ++j;
  65.             window += c[j];
  66.         }
  67.         long long ci = c[i];
  68.         ans += ci * (window - ci) + ci*(ci-1)/2;
  69.         window -= ci;
  70.     }
  71.     return ans;
  72. }
  73.  
  74. int main(){
  75.     rf();
  76.     cin >> n >> q;
  77.     cnt[1] = n;
  78.  
  79.     while (q--){
  80.         int op; cin >> op;
  81.         if (op == 1){
  82.             int a, b; cin >> a >> b;
  83.             merge_ab(cnt, a, b);
  84.         } else {
  85.             long long k; cin >> k;
  86.  
  87.             vector<int> val; val.reserve(cnt.size());
  88.             vector<long long> c; c.reserve(cnt.size());
  89.             long long total = 0;
  90.             for (auto &p : cnt){
  91.                 if (p.second == 0) continue;
  92.                 val.emplace_back(p.first);
  93.                 c.emplace_back(p.second);
  94.                 total += p.second;
  95.             }
  96.             long long total_pairs = total * (total - 1) / 2;
  97.             if (k > total_pairs){
  98.                 cout << -1 << nl;
  99.                 continue;
  100.             }
  101.             if (val.size() <= 1){
  102.                 cout << 0 << nl;
  103.                 continue;
  104.             }
  105.  
  106.             int l = 0, r = val.back() - val.front();
  107.             while (l < r){
  108.                 int mid = l + ((r - l) >> 1);
  109.                 if (count_pairs_leq(val, c, mid) >= k) r = mid;
  110.                 else l = mid + 1;
  111.             }
  112.             cout << l << nl;
  113.         }
  114.     }
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
10 15
2 45
1 1 1
1 1 1
1 1 1
2 10
2 9
1 1 2
2 5
2 1
2 13
1 1 1
1 2 2
2 6
2 1
2 4
stdout 
0
1
0
1
0
2
3
1
2
https://ideone.com/aHWXl5
language:
C++14 (gcc 8.3)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!