fork download 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15.  
  16. const int MAXN = 1e6 + 5;
  17. const int inf = 1e18;
  18. const int MOD = 1e9 + 7;
  19.  
  20. void FileInput(){
  21.     if(fopen(NAME".inp" , "r") == NULL)
  22.         freopen(NAME".inp" , "w" , stdout);
  23.     freopen(NAME".inp" , "r" , stdin);
  24.     freopen(NAME".out" , "w" , stdout);
  25. }
  26.  
  27. int k , n;
  28. int a[MAXN] , b[MAXN];
  29. int seat[MAXN];
  30. vector<pair<int , int>> query;
  31.  
  32. struct Cmp{
  33.     bool operator ()(pair<int , pair<int , int>> a , pair<int , pair<int , int>> b){
  34.         if(a.first == b.first)
  35.             return a.second.first > b.second.first;
  36.         return a.first < b.first;
  37.     }
  38. };
  39.  
  40. void solve(){
  41.     cin >> k >> n;
  42.     for(int i = 1 ; i <= n ; i++){
  43.         cin >> a[i] >> b[i];
  44.         query.push_back({a[i] , i});
  45.         query.push_back({b[i] , i});
  46.         seat[i] = -1;
  47.     }
  48.  
  49.  
  50.     sort(query.begin() , query.end());
  51.     // for(auto x : query)
  52.     //     cout << x.first << " " << x.second << endl;
  53.  
  54.     set<pair<int , int>> set1;
  55.     set<pair<int , pair<int , int>> , Cmp> set2;
  56.  
  57.     set1.insert({1 , k});
  58.     set2.insert({k , {1 , k}});
  59.  
  60.     for(auto temp : query){
  61.         int id = temp.second;
  62.         int x = seat[id];
  63.  
  64.         if(seat[id] == -1){ // đi vào
  65.             int l , r;
  66.             auto it = set2.end();
  67.             --it;
  68.  
  69.             l = (*it).second.first;
  70.             r = (*it).second.second;
  71.  
  72.             // cout << it -> first << " " << it -> second.first << " " << it -> second.second << endl;
  73.  
  74.             set2.erase(it);
  75.             set1.erase({l , r});
  76.  
  77.             int mid = (l + r) / 2;
  78.             seat[id] = mid;
  79.             // cout << "SEAT " << l << " " << r << " " << mid << " " << id << endl;
  80.  
  81.             if(l <= mid - 1){
  82.                 set1.insert({l , mid - 1});
  83.                 set2.insert({mid - l , {l , mid - 1}});
  84.             }
  85.  
  86.             if(mid + 1 <= r){
  87.                 set1.insert({mid + 1 , r});
  88.                 set2.insert({r - mid , {mid + 1 , r}});
  89.             }
  90.         }else if(seat[id] != -1){ // đi ra
  91.             auto it = set1.upper_bound({x , 0});
  92.             auto it2 = it;
  93.             if(!set1.empty()) it2--;
  94.  
  95.             // cout << "ERASE " << x << endl;
  96.  
  97.             pair<int , int> nwSeg = {x , x};
  98.             if(!set1.empty() && it != set1.end() && it -> first == x + 1){
  99.                 nwSeg.second = it -> second;
  100.  
  101.                 set2.erase({it->second - it->first + 1 , *it});
  102.                 set1.erase(it);
  103.             }
  104.  
  105.             if(!set1.empty() && it2 -> second == x - 1){
  106.                 nwSeg.first = it2 -> first;
  107.  
  108.                 set2.erase({(*it2).second - (*it2).first + 1 , *it2});
  109.                 set1.erase(*it2);
  110.             }
  111.  
  112.             set1.insert(nwSeg);
  113.             set2.insert({nwSeg.second - nwSeg.first + 1 , nwSeg});
  114.         }
  115.  
  116.         // for(auto x : set2)
  117.         //     cout << temp.first << " " << temp.second << " " << x.first << " " << x.second.first << " " << x.second.second << endl;
  118.  
  119.     }
  120.  
  121.     for(int i = 1 ; i <= n ; i++)
  122.         cout << seat[i] << " ";
  123. }
  124.  
  125. int32_t main(){
  126.     //FileInput();
  127.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  128.     int t = 1;
  129.     // cin >> t;
  130.     while(t--)
  131.         solve();
  132.     return 0;
  133. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BDTIRg
language:
C++14 (gcc 8.3)
created:
2 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!