Advertisement
Guest User

Untitled

a guest
Oct 21st, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define pb push_back
  5. #define mp make_pair
  6. #define f first
  7. #define s second
  8. #define int long long
  9. typedef long long ll;
  10. typedef pair<int,int>pii;
  11. #define MAXN 1123456
  12. #define INF INT_MAX/2
  13. #define MOD 1000000
  14.  
  15. int bit[MAXN];
  16. pair<int,pii> v[MAXN];
  17. int n;
  18.  
  19. int helpme[MAXN];
  20.  
  21. void upd(int a, int x){
  22. if(a==0)return;
  23. for(int i=a;i<MAXN;i+=(i&-i)){
  24. bit[i]=max(bit[i],x);
  25. }
  26. }
  27.  
  28. int get(int a){
  29. int resp=0;
  30. for(int i=a;i>0;i-=(i&-i)){
  31. resp=max(resp,bit[i]);
  32. }
  33. return resp;
  34. }
  35.  
  36. bool rev(pair<int,pii> a,pair<int,pii> b){
  37. return a.f>b.f;
  38. }
  39.  
  40. bool forcomp(pair<int,pii> a,pair<int,pii> b){
  41. return a.s.f<b.s.f;
  42. }
  43.  
  44.  
  45. int32_t main(){
  46. ios::sync_with_stdio(false);
  47. cin.tie(0);
  48.  
  49. cin>>n;
  50.  
  51. //ler entrada
  52. for(int i=0;i<n;i++){
  53. cin>>v[i].f;
  54. }
  55. for(int i=0;i<n;i++){
  56. cin>>v[i].s.f;
  57. }
  58. for(int i=0;i<n;i++){
  59. cin>>v[i].s.s;
  60. }
  61. //comprimir coordenada
  62. sort(v,v+n,forcomp);
  63. int mark=0;
  64. for(int i=0;i<n;i++){
  65. helpme[i]=mark;
  66. if(i==n-1||v[i+1].s.f!=v[i].s.f)mark++;
  67. }
  68. for(int i=0;i<n;i++){
  69. v[i].s.f=helpme[i];
  70. }
  71. //preparar pra bit
  72. sort(v,v+n,rev);
  73.  
  74. //rodar na bit
  75. int resp=0;
  76. queue<pii> q;
  77. for(int i=0;i<n;){
  78. if(get(MAXN-v[i].s.f-1)>v[i].s.s){
  79. resp++;
  80. }
  81. q.push(mp(MAXN-v[i].s.f,v[i].s.s));
  82. i++;
  83. while(i<n && v[i].f==v[i-1].f){
  84. if(get(MAXN-v[i].s.f-1)>v[i].s.s){
  85. resp++;
  86. }
  87. q.push(mp(MAXN-v[i].s.f,v[i].s.s));
  88. i++;
  89. }
  90. while(!q.empty()){
  91. pii aux=q.front();
  92. q.pop();
  93. upd(aux.f,aux.s);
  94. }
  95. }
  96.  
  97.  
  98. cout<<resp<<endl;
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement