Advertisement
SuitNdtie

Monkey not done

May 31st, 2019
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<queue>
  4. using namespace std;
  5. typedef long long int ll;
  6.  
  7. struct elem{
  8.     int u;
  9.     int h;
  10.     bool wis;
  11. };
  12. int const N = 200010;
  13. vector<pair<int,int> > vec[N];
  14.  
  15. int bsearch(int I,int high) //return idx where h = first at I
  16. {
  17.     int L = 0,R = vec[I].size()-1;
  18.     int idx;
  19.     int h = high;
  20.     while(L<=R){
  21.         int m = (L+R)/2;
  22.         int vh = vec[I][m].first;
  23.         if(vh > h){
  24.             idx = m;
  25.             R = m - 1;
  26.         }
  27.         else if(vh < h){
  28.             L = m + 1;
  29.         }
  30.         else if(vh == h){
  31.             return m;
  32.         }
  33.     }
  34.     return idx;
  35.     printf("Bsearch error (%d,%d)\n",I,high);
  36.     return -1;
  37. }
  38. int main()
  39. {
  40.     freopen("input1.txt","r",stdin);
  41.     int n,m,k;
  42.     scanf("%d %d %d",&m,&n,&k);
  43.     ll ban[n+1];
  44.     int ans[n+1];
  45.     for(int i = 1 ; i <= n ; i ++){
  46.         scanf("%lld",&ban[i]);
  47.         vec[i].push_back({0,0});
  48.         ans[i] = -1;
  49.     }
  50.  
  51.     for(int i = 1 ; i <= k ; i ++){
  52.         int u,h;
  53.         scanf("%d %d",&u,&h);
  54.         vec[u].push_back({h,1});
  55.         vec[u+1].push_back({h,-1});
  56.     }
  57.     int start;
  58.     scanf("%d",&start);
  59.  
  60.     for(int i = 1 ; i <= k ; i ++){
  61.         printf("Stick #%d : ",i);
  62.         for(int j = 0 ; j < vec[i].size() ; j ++){
  63.             printf(" (%d,%d)",vec[i][j].first , vec[i][j].second);
  64.         }
  65.         printf("\n");
  66.     }
  67.    // printf("%d -> %d",bsearch(4,10),vec[4][bsearch(4,10)]);
  68.    // return 0;
  69.     queue<elem> q;
  70.     q.push({start,0,true});
  71.     while(!q.empty()){
  72.         int u = q.front().u;
  73.         int h = q.front().h;
  74.         bool wis = q.front().wis;
  75.         printf("Test (%d,%d,%d)\n",u,h,wis?1:0);
  76.         q.pop();
  77.         int Hidx = bsearch(u,h);
  78.         if(Hidx == -1)return -1;
  79.         if(Hidx + 1 == vec[u].size()){
  80.             ans[u] = (wis?0:1);
  81.             continue;
  82.         }
  83.         if(wis){
  84.             if(u-1 >= 1)q.push({u-1,h,false});
  85.             if(u+1 <= n)q.push({u+1,h,false});
  86.         }
  87.         q.push({u + vec[u][Hidx+1].second , vec[u][Hidx+1].first , wis});
  88.     }
  89.     ll maxa = -1;
  90.     bool iswis;
  91.     for(int i = 1 ; i <= n ; i ++){
  92.         if(ans[i] != -1){
  93.             if(ban[i] > maxa){
  94.                 maxa = ban[i];
  95.                 iswis = ans[i] == 1;
  96.             }
  97.         }
  98.     }
  99.     printf("%lld\n%s",maxa,(iswis ? "USE" : "NO"));
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement