Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Panstwo
- {
- int nr;
- unsigned wspolczynnik;
- };
- int main()
- {
- ios_base::sync_with_stdio(false);
- unsigned n;cin>>n;
- unsigned ile=0;
- Panstwo* tab=new Panstwo[n];
- int indexy[1001];//przechowuje indeksy elementow /*zalozenie n<=1000*/
- for(unsigned i=0;i<n;++i)
- {
- cin>>tab[i].nr;
- cin>>tab[i].wspolczynnik;
- indexy[tab[i].nr]=i;//zeby latwiej bylo szukac to przypisane indeksy
- }
- unsigned m;cin>>m;
- for(unsigned j=0;j<m;++j)
- {
- unsigned p,w;
- cin>>p>>w;
- int szukany=indexy[p/*i*/];//index szukanego elementu
- tab[szukany].wspolczynnik=w;//zmiana wartosci
- unsigned ojciec=(szukany-1)/2;
- unsigned lsyn=(szukany*2)+1;
- unsigned psyn=lsyn+1;
- /*PRZESIEW*/ /*fatherV*/
- if(szukany>0&&w>tab[ojciec].wspolczynnik)
- {
- /*przesiew w gore*/
- while(szukany>0&&w>tab[ojciec].wspolczynnik)
- {
- swap(indexy[tab[ojciec].nr],indexy[tab[szukany].nr]);
- swap(tab[szukany],tab[ojciec]);//?
- ++ile;
- szukany=ojciec;
- --ojciec;
- ojciec/=2;
- }
- } /*V l-son*/ /*p- son*/
- else /*CHECKPOINT*/
- {
- if((lsyn<n&&w<tab[lsyn].wspolczynnik)||(psyn<n&&w<tab[psyn].wspolczynnik))
- {
- // int lsyn=szukany*2;--lsyn;int psyn=lsyn+1;
- while((lsyn<n&&w<tab[lsyn].wspolczynnik)||(psyn<n&&w<tab[psyn].wspolczynnik))
- {
- if(psyn<n&&tab[psyn].wspolczynnik>tab[lsyn].wspolczynnik)
- {
- swap(indexy[szukany],indexy[psyn]);
- swap(indexy[tab[szukany].nr],indexy[tab[psyn].nr]);
- ++ile;
- szukany=psyn;
- psyn*=2;
- ++psyn;
- }
- else
- {
- swap(indexy[szukany],indexy[lsyn]);
- swap(indexy[tab[szukany].nr],indexy[tab[lsyn].nr]);
- ++ile;
- szukany=lsyn;
- lsyn*=2;
- ++lsyn;/*ZMIENIAC TEZ PSYNA?*/
- }
- }
- }
- //else break;
- }
- }
- cout<<ile;
- delete [] tab;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement