Advertisement
wojiaocbj

Untitled

Jun 14th, 2022
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.99 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #include <math.h>
  5. #include <string.h>
  6. #pragma warning(disable:4996)
  7. #define MAX(a,b) (((a)>(b))?(a):(b))
  8. #define MIN(a,b) (((a)<(b))?(a):(b))
  9. typedef long long LL;
  10. typedef unsigned long long ULL;
  11. int compare(const void *p,const void *q){
  12.     int a = *(int *)p,b = *(int *)q;
  13.     if(a < b)return -1;
  14.     else if(a > b)return 1;
  15.     else return 0;
  16. }
  17. void *lowerbound(void *base,void *key,size_t count,size_t itemsize,int(*compare)(const void *,const void *)){
  18.     //assert(base && compare);
  19.     size_t lo = 0,hi = count - 1,mid = 0;
  20.     if(compare(key,(char *)base + hi * itemsize) > 0){
  21.         return (char *)base + count * itemsize;
  22.     }
  23.     char *pmid = 0;
  24.     while(lo < hi){
  25.         mid = (lo + hi) >> 1;
  26.         pmid = ((char *)base) + mid * itemsize;
  27.         if(compare(pmid,key) < 0){
  28.             lo = mid + 1;
  29.         }
  30.         else{
  31.             hi = mid;
  32.         }
  33.     }
  34.     return (char *)base + lo * itemsize;
  35. }
  36. void *upperbound(void *base,void *key,size_t count,size_t itemsize,int(*compare)(const void *,const void *)){
  37.     //assert(base && compare);
  38.     size_t lo = 0,hi = count - 1,mid;
  39.     if(compare(key,(char *)base + hi * itemsize) >= 0){
  40.         return (char *)base + count * itemsize;
  41.     }
  42.     char *pmid;
  43.     while(lo < hi){
  44.         mid = (lo + hi) >> 1;
  45.         pmid = ((char *)base) + mid * itemsize;
  46.         if(compare(pmid,key) <= 0){
  47.             lo = mid + 1;
  48.         }
  49.         else{
  50.             hi = mid;
  51.         }
  52.     }
  53.     return (char *)base + lo * itemsize;
  54. }
  55. int a[1919810] = {0};
  56. int main(){
  57.     int n,q,i,m;
  58.     scanf("%d",&n);
  59.     for(i = 0;i < n;i++){
  60.         scanf("%d",a + i);
  61.     }
  62.     scanf("%d",&q);
  63.     while(q--){
  64.         scanf("%d",&m);
  65.         int *pos = (int *)lowerbound(a,&m,n,sizeof(int),compare);
  66.         if(*pos == m){
  67.             printf("Yes %d\n",(int)(pos - a) + 1);
  68.         }
  69.         else{
  70.             puts("No");
  71.         }
  72.     }
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement