fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ms(s,n) memset(s,n,sizeof(s))
  5. #define all(a) a.begin(),a.end()
  6. #define present(t, x) (t.find(x) != t.end())
  7. #define sz(a) int((a).size())
  8. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  9. #define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
  10. #define pb push_back
  11. #define pf push_front
  12. #define fi first
  13. #define se second
  14. #define mp make_pair
  15.  
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. typedef long double ld;
  19. typedef pair<int,int> pi;
  20. typedef vector<int> vi;
  21. typedef vector<pi> vii;
  22.  
  23. const int MOD = (int) 1e9+7;
  24. const int INF = (int) 1e9+1;
  25. inline ll gcd(ll a,ll b){ll r;while(b){r=a%b;a=b;b=r;}return a;}
  26. inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
  27.  
  28. bool cmp(pair<pi,int> a, pair<pi, int > b){
  29. 	if(a.fi.fi != b.fi.fi)
  30. 		return a.fi.fi < b.fi.fi;
  31. 	return a.fi.se < b.fi.se;
  32. }
  33.  
  34. int main(){
  35. 	#ifndef ONLINE_JUDGE
  36. 	freopen("input.txt", "r", stdin);
  37. 	freopen("output.txt", "w", stdout);
  38. 	#endif
  39. 	int n; cin >>n;
  40. 	vector<pair<pi, int >> a(n);
  41. 	for(int i = 0; i < n; i++){
  42. 		cin >> a[i].fi.fi >> a[i].fi.se;
  43. 		a[i].se = i;
  44. 	}
  45. 	sort(all(a), cmp);
  46. 	// for(auto it : a){
  47. 	// 	cout << it.fi.fi <<" " << it.fi.se << endl;
  48. 	// }
  49. 	int cnt = 1;
  50. 	vi res(n, 0);
  51. 	multimap<int,int> mp;
  52. 	mp.insert({a[0].fi.se, 1});
  53. 	res[a[0].se] = 1;
  54. 	for(int i = 1; i < n; i++){
  55. 		int tmp = a[i].fi.fi;
  56. 		auto it = mp.lower_bound(tmp);
  57. 		if(it == mp.end()){
  58. 			res[a[i].se] = mp.rbegin()->se;
  59. 			auto it2 = mp.end();
  60. 			mp.erase(--it2);
  61. 			mp.insert({a[i].fi.se, res[a[i].se]});
  62. 		}
  63. 		else if(it == mp.begin()){
  64. 			res[a[i].se] = ++cnt;
  65. 			mp.insert({a[i].fi.se, cnt});
  66. 		}
  67. 		else{
  68. 			--it;
  69. 			res[a[i].se] = it->se;
  70. 			mp.erase(it);
  71. 			mp.insert({a[i].fi.se, res[a[i].se]});
  72. 		}
  73. 	}
  74. 	cout << cnt << endl;
  75. 	for(int x : res){
  76. 		cout << x << " ";
  77. 	}
  78. 	return 0;
  79. }
Runtime error #stdin #stdout 0.01s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qrudca
language:
C++14 (gcc 8.3)
created:
3 years 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!