fork download
copy 
  1. /*
  2.   Zenit CK 2011/2012, uloha h)
  3.   Riesenie by Zemco.
  4.  
  5.   Maxovy intervalovy strom, ktory dokaze spracovat
  6.   kazdu z operacii v case log(N)
  7.  
  8.   Implementovany klasicky haldovo v poli. ak je w vrchol potom rodic je w/2 a deti 2*w, 2*w+1.
  9.   koren ma index 1, listy N az 2N-1 vratane.
  10.  
  11.   Vid vzorak KSP, rocnik 2006/2007 (24), 1. kolo zimnej casti, uloha 6 o Novom jorku
  12.    */
  13.  
  14. #include<cstdio>
  15. //pole pre strom, dlzka dolneho poschodia
  16. int I[250000],dlzka,N,K;
  17. int mx(int a, int b){ return a < b ? b : a; }
  18.  
  19. void update(int w, int nw){
  20.   //ww - index v poli vo vrchole, kde momentalne sme
  21.   int ww = w+N-1;
  22.   //updatneme list
  23.   I[ww] = nw;
  24.   while(ww > 1){
  25.     ww/=2;
  26.     //upravime cestu od listu ku korenu
  27.     I[ww] = mx(I[ww*2],I[ww*2+1]);
  28.   }
  29. }
  30.  
  31. //index pola, zodpovedajuci aktualnemu vrcholu. dlzka useku pod tymto vcholom. zelana hodnota
  32. //predpoklad: v podstrome je aspon jedna hodnota aspon 'val'.
  33. int search(int w, int length, int val){
  34.   //uz sme v liste
  35.   if (length == 1) return w-N+1;
  36.   //nachadza sa nejaka vyssia hodnota v lavom podstrome?
  37.   if (I[w*2] >= val) return search(w*2,length/2,val);
  38.   else return search(w*2+1,length/2,val);
  39. }
  40.  
  41. int main(){
  42.   scanf("%d %d ",&dlzka,&K);
  43.   N = 1;
  44.   //najdeme najmensiu mocninu dvoch <= N
  45.   while (N < dlzka) N*=2;
  46.  
  47.   //spracovame poziadavky
  48.   for(int i=0;i<K;i++){
  49.     int op;
  50.     scanf("%d ",&op);
  51.     if (op == 1){
  52.       int w,nw;
  53.       scanf("%d %d ",&w,&nw);
  54.       //updatneme zamestnanca w na hodnotu spokojnosti nw
  55.       update(w,nw);
  56.     }else{
  57.       int val;
  58.       scanf("%d ",&val);
  59.       //najdeme prislusneho zamestnanca
  60.       if (val > I[1]) printf("nikto\n");
  61.       else printf("%d\n",search(1,N,val));
  62.     }
  63.   }
  64.   return 0;
  65. }
Success #stdin #stdout 0.02s 3700KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GJN1E
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

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!