fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using int64 = long long;
  5.  
  6. // Đếm số cặp có |x - y| <= d, làm việc trên các giá trị phân biệt
  7. static inline long long count_at_most(const vector<int>& val,
  8.                                       const vector<long long>& freq,
  9.                                       long long d) {
  10.     int m = (int)val.size();
  11.     vector<long long> pref(m + 1, 0);
  12.     for (int i = 0; i < m; ++i) pref[i + 1] = pref[i] + freq[i];
  13.  
  14.     long long res = 0;
  15.     int j = 0;
  16.     for (int i = 0; i < m; ++i) {
  17.         if (j < i) j = i;
  18.         while (j + 1 < m && (long long)val[j + 1] - val[i] <= d) ++j;
  19.         long long ci = freq[i];
  20.         long long sum_right = pref[j + 1] - pref[i + 1]; // tổng f_{i+1..j}
  21.         res += ci * sum_right + ci * (ci - 1) / 2;       // cặp khác nhóm + trong nhóm
  22.     }
  23.     return res;
  24. }
  25.  
  26. int main() {
  27.     ios::sync_with_stdio(false);
  28.     cin.tie(nullptr);
  29.  
  30.     int N, Q;
  31.     if (!(cin >> N >> Q)) return 0;
  32.  
  33.     // multiset giá trị: lưu theo (giá trị -> tần suất)
  34.     map<int, long long> cnt;
  35.     cnt[1] = N;
  36.  
  37.     while (Q--) {
  38.         int tp; 
  39.         cin >> tp;
  40.         if (tp == 1) {
  41.             int a, b; cin >> a >> b;
  42.             // giảm a, b
  43.             auto dec = [&](int x){
  44.                 auto it = cnt.find(x);
  45.                 if (it == cnt.end() || it->second == 0) return; // input đảm bảo hợp lệ
  46.                 if (--(it->second) == 0) cnt.erase(it);
  47.             };
  48.             dec(a); dec(b);
  49.             cnt[a + b]++; // tăng a+b
  50.         } else {
  51.             long long k; cin >> k;
  52.  
  53.             // gom về 2 mảng đã sort sẵn
  54.             vector<int> val; val.reserve(cnt.size());
  55.             vector<long long> freq; freq.reserve(cnt.size());
  56.             long long n = 0;
  57.             for (auto &p : cnt) {
  58.                 val.push_back(p.first);
  59.                 freq.push_back(p.second);
  60.                 n += p.second;
  61.             }
  62.             // biên nhị phân
  63.             long long lo = 0, hi = val.back() - val.front(); // khoảng cách tối đa
  64.             // bảo toàn: tổng số cặp = nC2, k luôn hợp lệ theo đề
  65.             while (lo < hi) {
  66.                 long long mid = (lo + hi) >> 1;
  67.                 if (count_at_most(val, freq, mid) >= k) hi = mid;
  68.                 else lo = mid + 1;
  69.             }
  70.             cout << lo << '\n';
  71.         }
  72.     }
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
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
copy 
0
1
0
1
0
2
3
1
2
https://ideone.com/QwfQye
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!