fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll nmax=1e5+5;
  5. ll n,m,k[nmax]; ll sz;
  6. struct Node {
  7.     ll key, prior;
  8.     ll cnt, size;
  9.     Node *l, *r;
  10.     Node(ll k): key(k), prior(rand()), cnt(1), size(1), l(nullptr), r(nullptr) {}
  11. };
  12.  
  13. ll getSize(Node* t) { return t ? t->size : 0; }
  14. void upd(Node* t) { if (t) t->size = getSize(t->l) + getSize(t->r) + t->cnt; }
  15.  
  16. Node* merge(Node* l, Node* r) {
  17.     if (!l || !r) return l ? l : r;
  18.     if (l->prior > r->prior) {
  19.         l->r = merge(l->r, r); upd(l); return l;
  20.     } else {
  21.         r->l = merge(l, r->l); upd(r); return r;
  22.     }
  23. }
  24.  
  25. void split(Node* t, ll key, Node* &l, Node* &r) {
  26.     if (!t) l = r = nullptr;
  27.     else if (key < t->key) {
  28.         split(t->l, key, l, t->l);
  29.         r = t; upd(t);
  30.     } else {
  31.         split(t->r, key, t->r, r);
  32.         l = t; upd(t);
  33.     }
  34. }
  35.  
  36. struct OrderedSet {
  37.     Node* root = nullptr;
  38.  
  39.     void insert(ll key) {
  40.         Node *l, *r;
  41.         split(root, key, l, r);
  42.         Node *tl, *tr;
  43.         split(l, key-1, tl, tr);
  44.         if (tr) { tr->cnt++; upd(tr); l = merge(tl, tr); }
  45.         else l = merge(tl, new Node(key));
  46.         root = merge(l, r); upd(root);
  47.     }
  48.  
  49.     void erase(ll key) {
  50.         Node *l, *r;
  51.         split(root, key, l, r);
  52.         Node *tl, *tr;
  53.         split(l, key-1, tl, tr);
  54.         if (tr) {
  55.             if (tr->cnt > 1) { tr->cnt--; upd(tr); }
  56.             else { delete tr; tr = nullptr; }
  57.         }
  58.         l = merge(tl, tr);
  59.         root = merge(l, r); upd(root);
  60.     }
  61.  
  62.     ll order_of_key(ll x) {
  63.         Node* t = root;
  64.         ll res = 0;
  65.         while (t) {
  66.             if (x <= t->key) t = t->l;
  67.             else {
  68.                 res += getSize(t->l) + t->cnt;
  69.                 t = t->r;
  70.             }
  71.         }
  72.         return res;
  73.     }
  74.  
  75.     ll find_by_order(ll k) {
  76.         Node* t = root;
  77.         while (t) {
  78.             if (k < getSize(t->l)) t = t->l;
  79.             else if (k < getSize(t->l) + t->cnt) return t->key;
  80.             else {
  81.                 k -= getSize(t->l) + t->cnt;
  82.                 t = t->r;
  83.             }
  84.         }
  85.         return -1; // không tồn tại
  86.     }
  87.  
  88.     ll size() { return getSize(root); }
  89.     bool empty() { return size() == 0; }
  90. };
  91.  
  92. /*
  93.     OrderedSet os;
  94.     os.insert(5);
  95.     os.insert(2);
  96.     os.insert(7);
  97.     os.insert(5); // cho phép trùng
  98.  
  99.     cout << "size = " << os.size() << "\n"; // 4
  100.     cout << "order_of_key(6) = " << os.order_of_key(6) << "\n"; // số phần tử < 6
  101.     cout << "find_by_order(1) = " << os.find_by_order(1) << "\n"; // phần tử có index 1
  102.  
  103.     os.erase(5);
  104.     cout << "size sau erase = " << os.size() << "\n";
  105.     */
  106. OrderedSet os;
  107. void inp(){
  108.     cin>>n>>m;
  109.     for(ll i=1;i<=m;++i)
  110.         cin>>k[i];
  111.     return;
  112. }
  113. ll res[nmax];
  114. ll BIT[nmax];
  115. map<ll,ll> mp;
  116. void update(ll s){
  117.     while(s<nmax){
  118.         ++BIT[s];
  119.         s+=(s&(-s));
  120.     }
  121.     return;
  122. }
  123. ll get(ll s){
  124.     ll sum=0;
  125.     while(s>0LL){
  126.         sum+=BIT[s];
  127.         s-=(s&(-s));
  128.     }
  129.     return sum;
  130. }
  131. void prepare(){
  132.     for(ll i=1;i<=m;++i){
  133.         ll l=1,r=(n*(n-1LL))/2LL,mid;
  134.         while(l<=r){
  135.             mid=(l+r)/2LL;
  136.             ll sl=os.order_of_key(mid+1LL);
  137.             //cout<<i<<' '<<mid<<' '<<sl<<" ok \n";
  138.             if(mid-sl>=k[i]){
  139.                 res[i]=mid;
  140.                 r=mid-1LL;
  141.             }else
  142.                 l=mid+1LL;
  143.  
  144.         }
  145.         os.insert(res[i]);
  146.     }
  147.     //cout<<"WWW\n";
  148.     return;
  149. }
  150. void solve(){
  151.     for(ll i=1;i<=m;++i){
  152.         ll l=1,r=n,mid;
  153.         ll id=0;
  154.         while(l<=r){
  155.             mid=(l+r)/2LL;
  156.             if(n*mid-(mid*(mid+1LL))/2LL < res[i]){
  157.                 id=mid;
  158.                 l=mid+1LL;
  159.             }else
  160.                 r=mid-1LL;
  161.         }
  162.         res[i]-=(n*id-(id*(id+1LL))/2LL);
  163.         cout<<id+1LL<<' '<<id+1LL+res[i]<<'\n';
  164.     }
  165.     return;
  166. }
  167. int main(){
  168.     ios_base::sync_with_stdio(0);
  169.     cin.tie(0); cout.tie(0);
  170.     inp();
  171.     prepare();
  172.     solve();
  173.     return 0;
  174. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GxBgvb
language:
C++14 (gcc 8.3)
created:
14 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!