fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long mod = 1e9 + 7;
  5. const double eps = 1e-9;
  6. const double PI = atan(1.0);
  7. #define readFile freopen("input","r",stdin);
  8. #define writeFile freopen("output","w",stdout);
  9. #define fastIO ios::sync_with_stdio(0);
  10. typedef pair<int,int> ii;
  11. typedef unsigned long long ULL;
  12.  
  13. const int N = 100000;
  14. int tree [N*4];
  15. map<int,int> hash;
  16. int lazy[N*4];
  17. ii queries[N];
  18. int n;
  19.  
  20. int query(int node,int l,int r,int ll,int rr){
  21.     if (lazy[node]){
  22.         tree[node] = lazy[node];
  23.         if (l!=r){
  24.             lazy[node<<1] = lazy[node];
  25.             lazy[node<<1|1] = lazy[node];
  26.         }
  27.         lazy[node]=0;
  28.     }
  29.     if (l>rr || r<ll) return 1;
  30.     if (l>=ll && r<=rr){
  31.  
  32.         return tree[node];
  33.     }
  34.     int mid = (l+r)>>1;
  35.     return tree[node] = query(node<<1,l,mid,ll,rr)&query(node<<1|1,mid+1,r,ll,rr);
  36. }
  37.  
  38. int update(int node,int l,int r,int ll,int rr){
  39.     if (lazy[node]){
  40.         tree[node] = lazy[node];
  41.         if (l!=r){
  42.             lazy[node<<1] = lazy[node];
  43.             lazy[node<<1|1] = lazy[node];
  44.         }
  45.         lazy[node]=0;
  46.     }
  47.     if (l>rr || r<ll) return tree[node];
  48.     if (l>=ll && r<=rr){
  49.         if (l!=r){
  50.             lazy[node<<1]=1;
  51.             lazy[node<<1|1]=1;
  52.         }
  53.         return tree[node] = 1;
  54.     }
  55.     int mid = (l+r)>>1;
  56.     tree[node] = update(node<<1,l,mid,ll,rr)&update(node<<1|1,mid+1,r,ll,rr);
  57. }
  58.  
  59.  
  60.  
  61. int main(){
  62. #ifndef ONLINE_JUDGE
  63.     readFile;
  64. #endif
  65.     fastIO;
  66.     int t; cin>>t;
  67.     while(t--){
  68.         cin>>n;
  69.         hash.clear();
  70.         memset(lazy,0,sizeof(lazy));
  71.         memset(tree,0,sizeof(tree));
  72.         vector<int> tmp;
  73.         for(int i=1;i<=n;i++){
  74.             int a,b; cin>>a>>b;
  75.             if (a>b) swap(a,b);
  76.             queries[i] = make_pair(a,b);
  77.             tmp.push_back(a);
  78.             tmp.push_back(b);
  79.         }
  80.         sort(tmp.begin(),tmp.end());
  81.         int pointer=1;
  82.         for(int i=0;i<tmp.size();i++){
  83.             if (!hash[tmp[i]]) 
  84.                 hash[tmp[i]] = pointer++;
  85.         }
  86.         int res=0;
  87.         for(int i=n;i>=1;i--){
  88.             if (!query(1,1,pointer,hash[queries[i].first],hash[queries[i].second])){
  89.                 res++;
  90.                 update(1,1,pointer,hash[queries[i].first],hash[queries[i].second]);
  91.             }
  92.         }
  93.         cout<<res<<"\n";
  94.     }
  95. }
Success #stdin #stdout 0s 7368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/p2jcGG
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!