fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define endl "\n"
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define ub upper_bound
  7. #define in insert
  8. #define ump unordered_map
  9. #define yes cout<<"Yes"<<"\n"
  10. #define no cout<<"No"<<"\n"
  11. const ll M = 998244353;
  12. const ll INF = LLONG_MAX;
  13. const int dx[] = {-1, 1, 0, 0};
  14. const int dy[] = {0, 0, -1, 1};
  15. using namespace std;
  16. const int N = 2e5+10;
  17.  
  18. int main() {
  19.     ios_base::sync_with_stdio(false);
  20.     cin.tie(0);
  21.     ll n;cin>>n;
  22.     vector<pair<pair<ll,ll>,ll >> arr;
  23.     multiset<pair<ll,ll>> hotel;
  24.     for(ll i=0;i<n;i++) {
  25.         ll a,d;cin>>a>>d;arr.pb({{a,d}, i});
  26.     }
  27.     sort(arr.begin(), arr.end());
  28.     ll r=1;
  29.     vector<pair<ll,ll>> ans; ll ct=0;
  30.     for(auto el: arr) {
  31.         ll arrival = el.first.first;
  32.         ll dep = el.first.second;
  33.         if(hotel.empty()) {
  34.             r=1;
  35.             hotel.in({dep, r});
  36.             ans.pb({el.second, r});
  37.             r++;
  38.         } else {
  39.             auto fd=hotel.begin();
  40.             if(fd->first<arrival) {
  41.                 ll room=fd->second;
  42.                 hotel.erase(fd);
  43.                 hotel.in({dep,room});
  44.                 ans.pb({el.second, room});
  45.             } else {
  46.                 hotel.in({dep, r});
  47.                 ans.pb({el.second, r});
  48.                 r++;
  49.             }
  50.         }
  51.         ct=max(ct,(ll)hotel.size());
  52.     }
  53.     cout<<ct<<endl;
  54.     sort(ans.begin(), ans.end());
  55.     for(auto el: ans) cout<<el.second<<" ";cout<<endl;
  56. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3
1 2
2 4
4 4
stdout
copy 
2
1 2 1
https://ideone.com/r0V72D
language:
C++14 (gcc 8.3)
created:
23 hours 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!