Advertisement
zhbdripon

Untitled

Aug 18th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll              long long
  6. #define pb              push_back
  7. #define mp              make_pair
  8. #define ff              first
  9. #define ss              second
  10. #define SQ(x)           ((x)*(x))
  11. #define LCM(x,y)        (((x)/gcd((x),(y)))*(y))
  12. #define PI              acos(-1)
  13. #define SZ(x)           x.size() - 1
  14. #define waa             printf("Ripon\n")
  15. #define mem(a,b)        memset(a,b,sizeof(a))
  16. #define rep(i,a,n)      for(int i=(int)(a);i<=(int)(n);i++)
  17. #define per(i,n,a)      for(int i=(int)(n);i>=(int)(a);i--)
  18. #define SC              scanf
  19. #define PF              printf
  20. #define sc(x)           scanf("%d",&x)
  21. #define scl(x)          scanf("%lld",&x)
  22. #define scc(x,y)        scanf("%d %d",&x,&y)
  23. #define sccl(x,y)       scanf("%lld %lld",&x,&y)
  24. #define sccc(x,y,z)     scanf("%d %d %d",&x,&y,&z)
  25. #define scccl(x,y,z)    scanf("%lld %lld %lld",&x,&y,&z)
  26. //Grid tour
  27. int dx[] = { 0, 1, 0, -1, -1, 1, 1, -1 };
  28. int dy[] = { 1, 0, -1, 0, -1, -1, 1, 1 };
  29. int kx[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
  30. int ky[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
  31. //functions
  32. inline ll gcd(ll a,ll b){a =fabs(a);b=fabs(b);while(b){a=a%b;swap(a,b);}return a;}
  33. inline ll bigmod(ll a,ll p,ll m){ll res=1% m,x=a%m;while(p){if(p&1)res=(res*x)%m;x=(x*x)%m;p>>= 1;}return res;}
  34. int overlap(int rs,int re,int qs,int qe){ if(rs>qe or re<qs) return 0; else if(qs<=rs and re<=qe) return 1; else return 2;}
  35.  
  36.  
  37. #define mod 10000007
  38. #define eps 1e-9
  39. #define inf INT_MAX
  40. #define mx 30009
  41. struct DATA{};
  42.  
  43. int tree[mx*3];
  44. int arr[] = {0 ,2 ,1, 4, 5, 1, 3, 3};
  45. int lft,rgt,n=7;
  46. ll res;
  47.  
  48. int build(int node,int st,int en){
  49.     if(st==en){
  50.         return tree[node] = arr[st];
  51.     }
  52.     int lchild = node * 2;
  53.     int rchild = lchild + 1;
  54.     int mid = (st+en) / 2;
  55.     return tree[node] = min(build(lchild,st,mid),build(rchild,mid+1,en));
  56. }
  57.  
  58. int query_left(int node,int st,int en,int lf,int rt,int val,int in){
  59.     cout<<"call "<<st<<" "<<en<<endl;
  60.     int op = overlap(st,en,lf,rt);
  61.     if(op==0) return INT_MAX;
  62.     else if(st==en){
  63.         return arr[st];
  64.     }else if(op==1 and tree[node]>=val){
  65.         cout<<"yappi "<<st<<" "<<en<<" node = "<<node<<" tree[node] = "<<tree[node]<<" val = "<<val<<endl;
  66.         return tree[node];
  67.     }
  68.  
  69.     int lchild = node * 2;
  70.     int rchild = lchild + 1;
  71.     int mid = (st+en) / 2;
  72.  
  73.     int L=INT_MAX,R=INT_MAX;
  74.  
  75.     R = query_left(rchild,mid+1,en,lf,rt,val,in);
  76.  
  77.     if(R>=val and R!=INT_MAX){
  78.         lft = min(lft,mid+1);
  79.     }else if(mid+1<=in){
  80.         return INT_MAX;
  81.     }
  82.  
  83.     cout<<st<<" "<<en<<" After R lft = "<<lft<<endl;
  84.  
  85.     L = query_left(lchild,st,mid,lf,rt,val,in);
  86.  
  87.     if(L>=val and L!=INT_MAX){
  88.         lft = min(lft,st);
  89.     }else return INT_MAX;
  90.  
  91.     cout<<st<<" "<<en<<" After L lft = "<<lft<<endl;
  92.  
  93.     return min(R,L);
  94.  
  95.  
  96.  
  97.  
  98. }
  99.  
  100.  
  101. void solve(int T){
  102.  
  103.     rep(i,1,n*3) tree[i] = INT_MAX;
  104.     build(1,1,n);
  105.     cout<<tree[6]<<endl;
  106.     int i = 4;
  107.     lft=rgt=i;
  108.     query_left(1,1,n,1,i,arr[i],i);
  109.  
  110.     cout<<lft<<" "<<rgt<<endl;
  111.  
  112.     cout<<endl;
  113.  
  114. }
  115.  
  116.  
  117. int main(){
  118.     //freopen("file.txt","r",stdin);
  119.     //freopen("out.txt","w",stdout);
  120.     int T = 1;
  121.     //sc(T);
  122.     for(int i = 1;i<=T;i++) solve(i);
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement