fork download
copy 
  1.  
  2.  
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include <map>
  5. #include <set>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <fstream>
  9. #include <cmath>
  10. #include <ostream>
  11.  
  12. using namespace std;
  13.  
  14. struct treap
  15.  
  16. {
  17. 	long long meaning, n, k,minzn,minpl;
  18. 	treap *l, *r, *pr;
  19. };
  20. vector <treap*> obratvspomogvector,obratichodvect;
  21. treap *korendereva;
  22. treap *obratkorendereva;
  23. long long n1rab = 1;
  24. void postroenie_dereva(long long n1)
  25.  
  26. {
  27. 	n1rab = 1;
  28. 	while (n1rab<n1)
  29. 	{
  30. 		n1rab *= 2;
  31. 	}
  32.  
  33. 	vector <treap*> vspomogvector(n1rab + 1), ichodvect;
  34.             obratvspomogvector.resize(n1rab+1);
  35. 	for (long long i = 1; i <= n1rab; i++)
  36. 	{
  37. 		treap *m = new treap();
  38. 		vspomogvector[i] = m;
  39. 		if (i <= n1) {
  40.  
  41. 		            scanf("%lld", &((vspomogvector[i])->minzn));
  42. 			((vspomogvector[i])->minpl) = i;
  43. 			((vspomogvector[i])->n) = i;
  44. 			((vspomogvector[i])->k) = i;
  45. 			((vspomogvector[i])->meaning)=1;
  46. 		}
  47. 		if (i>n1)
  48. 		{
  49. 			((vspomogvector[i])->meaning) = 1;
  50.                                      ((vspomogvector[i])->minpl) = i;
  51. 			((vspomogvector[i])->minzn) = 1000;
  52. 			((vspomogvector[i])->n) = i;
  53. 			((vspomogvector[i])->k) = i;
  54. 		}
  55.  
  56. 		(vspomogvector[i])->l = NULL;
  57. 		(vspomogvector[i])->r = NULL;
  58.  
  59. 		ichodvect.push_back(vspomogvector[i]);
  60. 		//printf("info %d %d\n", 16, (*(ichodvect.end() - 1))->meaning);
  61. 	}
  62.  
  63.  
  64. for (long long j = 1; j <= n1rab; j++)
  65. 	{
  66. 	treap *m = new treap();
  67. 		obratvspomogvector[j] = m;
  68.  
  69.  
  70. 			((obratvspomogvector[j])->minpl) = j;
  71. 			((obratvspomogvector[j])->n) = j;
  72. 			((obratvspomogvector[j])->k) = j;
  73. 		((obratvspomogvector[j])->minzn) =((vspomogvector[(n1rab-j+1)])->minzn) ;
  74.  
  75. 			((obratvspomogvector[j])->meaning) = 1;
  76.  
  77.  
  78.  
  79.  
  80.  
  81. 		(obratvspomogvector[j])->l = NULL;
  82. 		(obratvspomogvector[j])->r = NULL;
  83.                        // printf("%lld \n",((obratvspomogvector[j])->minzn));	
  84.                         obratichodvect.push_back(obratvspomogvector[j]);
  85. 	}
  86.  
  87.  
  88.  
  89. 	long long t = n1rab;
  90. 	long long chethik = n1rab;
  91.  
  92. 	while (t != 1)
  93.  
  94. 	{
  95. 		for (long long i = 1; i <= (t / 2); i++)
  96. 		{
  97. 			treap *m = new treap();
  98. 			long long x = vspomogvector[1]->meaning;
  99. 			vspomogvector[i] = m;
  100. 			//printf("%d %d error \n", (vspomogvector[1])->meaning, (vspomogvector[2])->meaning);
  101. 			if (i == 1) {
  102. 				((vspomogvector[1])->meaning) = x + (((vspomogvector[2])->meaning));
  103. 			}
  104. 			else {
  105. 				(vspomogvector[i])->meaning = (((vspomogvector[2 * i - 1])->meaning) + ((vspomogvector[2 * i])->meaning));
  106. 			}
  107. 			/*changed to ichodvect; chetchik to t; = deleted*/ ((vspomogvector[i])->l) = *(((ichodvect.end()) -= ((t))) + (i - 1));
  108. 			((vspomogvector[i])->r) = *(((ichodvect.end()) -= ((t))) + (i));
  109.  
  110. 			(((vspomogvector[i])->l)->pr) = m;
  111. 			(((vspomogvector[i])->r)->pr) = m;
  112. 			ichodvect.push_back(vspomogvector[i]);
  113. 			//printf("info %d %d\n", t, (vspomogvector[i])->meaning);
  114. 			//printf("info %d %d\n", t, (*(ichodvect.end() - 1))->meaning);
  115. 		}
  116.  
  117. 		t = t / 2;
  118. 	}
  119. 	/* if (n1 == 1)
  120. 	{
  121. 	treap*m = new treap();
  122. 	vspomogvector[n1] = m;
  123. 	ichodvect.push_back(vspomogvector[n1]);
  124. 	((vspomogvector[n1])->l) = NULL;
  125. 	((vspomogvector[n1])->r) = NULL;
  126. 	}*/
  127. 	korendereva = (*(ichodvect.end() - 1));
  128. }
  129.  
  130.  
  131.  
  132. treap*a = korendereva;
  133.  
  134.  
  135.  
  136.  
  137. void zapolnenie(treap* v)
  138. { 
  139.       if ((v->l)!=NULL)
  140.  
  141.            {if (((v->l)->l)!=NULL)
  142.  
  143.             {zapolnenie(v->l);
  144.  
  145.             zapolnenie(v->r);}
  146.  
  147.                  if (((v->l)->minzn)<((v->r)->minzn))
  148.                  {(v->minzn)=((v->l)->minzn);
  149.                  (v->minpl)=((v->l)->minpl);}
  150.                  else
  151.                 {(v->minzn)=((v->r)->minzn);
  152.                  (v->minpl)=((v->r)->minpl);}
  153.  
  154.      (v->n)=((v->l)->n);
  155.      (v->k)=((v->r)->k);}
  156. else
  157. {(v->l)=NULL;}
  158. korendereva=korendereva;}
  159.  
  160. void printtt(treap* p1) {
  161. zapolnenie(korendereva);
  162. if (p1!= NULL) {
  163. printtt(p1->l);
  164. if (p1->meaning != 8) {
  165. printf("info %d %d info\n", (p1->pr)->minzn,(p1->pr)->minpl);
  166. }
  167. printtt(p1->r);
  168. }
  169. }
  170.  
  171.  
  172.  
  173. void obratpostroenie_dereva(long long obratn1)
  174. {
  175. 	long long obratt = n1rab;
  176. 	long long obratchethik = n1rab;
  177.  
  178. 	while (obratt != 1)
  179.  
  180. 	{
  181. 		for (long long obrati = 1; obrati <= (obratt / 2); obrati++)
  182. 		{
  183. 			treap *obratm = new treap();
  184. 			long long obratx = obratvspomogvector[1]->meaning;
  185. 			obratvspomogvector[obrati] = obratm;
  186. 			//printf("%d %d error \n", (vspomogvector[1])->meaning, (vspomogvector[2])->meaning);
  187. 			if (obrati == 1) {
  188. 				((obratvspomogvector[1])->meaning) = obratx + (((obratvspomogvector[2])->meaning));
  189. 			}
  190. 			else {
  191. 				(obratvspomogvector[obrati])->meaning = (((obratvspomogvector[2 * obrati - 1])->meaning) + ((obratvspomogvector[2 * obrati])->meaning));
  192. 			}
  193. 			/*changed to ichodvect; chetchik to t; = deleted*/ ((obratvspomogvector[obrati])->l) = *(((obratichodvect.end()) -= ((obratt))) + (obrati - 1));
  194. 			((obratvspomogvector[obrati])->r) = *(((obratichodvect.end()) -= ((obratt))) + (obrati));
  195.  
  196. 			(((obratvspomogvector[obrati])->l)->pr) = obratm;
  197. 			(((obratvspomogvector[obrati])->r)->pr) = obratm;
  198. 			obratichodvect.push_back(obratvspomogvector[obrati]);
  199. 			//printf("info %d %d\n", t, (vspomogvector[i])->meaning);
  200. 			//printf("info %d %d\n", t, (*(ichodvect.end() - 1))->meaning);
  201. 		}
  202.  
  203. 		obratt = obratt / 2;
  204. 	}
  205. 	/* if (n1 == 1)
  206. 	{
  207. 	treap*m = new treap();
  208. 	vspomogvector[n1] = m;
  209. 	ichodvect.push_back(vspomogvector[n1]);
  210. 	((vspomogvector[n1])->l) = NULL;
  211. 	((vspomogvector[n1])->r) = NULL;
  212. 	}*/
  213. 	obratkorendereva = (*(obratichodvect.end() - 1));
  214. }
  215.  
  216.  
  217. treap*obrata = obratkorendereva; 
  218.  
  219.  
  220.  
  221.  
  222. void obratzapolnenie(treap* obratv)
  223. { 
  224.       if ((obratv->l)!=NULL)
  225.  
  226.            {if (((obratv->l)->l)!=NULL)
  227.  
  228.             {zapolnenie(obratv->l);
  229.  
  230.             zapolnenie(obratv->r);}
  231.  
  232.                  if (((obratv->l)->minzn)<((obratv->r)->minzn))
  233.                  {(obratv->minzn)=((obratv->l)->minzn);
  234.                  (obratv->minpl)=((obratv->l)->minpl);}
  235.                  else
  236.                 {(obratv->minzn)=((obratv->r)->minzn);
  237.                  (obratv->minpl)=((obratv->r)->minpl);}
  238.  
  239.      (obratv->n)=((obratv->l)->n);
  240.      (obratv->k)=((obratv->r)->k);}
  241. else
  242. {(obratv->l)=NULL;}
  243. obratkorendereva=obratkorendereva;}
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250. void obratprinttt(treap* obratp1) {
  251. obratzapolnenie(obratkorendereva);
  252. if (obratp1!= NULL) {
  253. obratprinttt(obratp1->l);
  254. if (obratp1->meaning != 8) {
  255. printf("info %d %d info\n", (obratp1->pr)->minzn,(obratp1->pr)->minpl);
  256. }
  257. printtt(obratp1->r);
  258. }
  259. }
  260.  
  261.  
  262. treap* minimum(treap* c2,treap* d2)
  263. {if ((c2->minzn)>(d2->minzn))
  264.   {return(d2);}
  265. else
  266.   {return(c2);};}
  267.  
  268.  
  269.  
  270.  
  271. treap* min(long long q3, treap* uzel)
  272.  
  273. {if (q3=((uzel->k)-(uzel->n)+1))
  274.     {return(uzel);}
  275.  
  276. if  ((((uzel->l)->k)-((uzel->l)->n)+1)>q3)
  277. {return (min(q3,(uzel->l))); }
  278. else
  279. {return minimum((uzel->l),min(q3-((uzel->l)->k),uzel->r));}
  280. ;}
  281.  
  282.  
  283.  
  284.  
  285. treap* iskatotrezok(long long c1,long long d1,treap* verch1)
  286. {if ((c1<=(verch1->n))&&((verch1->k)<=d1))
  287.        {return(verch1);}
  288. else
  289. {treap* v2=iskatotrezok(c1,d1,(verch1->l));
  290.  treap* v3=iskatotrezok(c1,d1,(verch1->r));
  291. if (((v2->k)-(v2->n))>((v3->k)-(v3->n)))
  292. {return v2;}
  293. else
  294. {return v3;}
  295. ;}
  296. ;}
  297.  
  298.  
  299.  
  300.  
  301. treap* poisk_legko(long long c,long long d)
  302. {
  303. treap* verchf;
  304. treap* prmin;
  305. treap* promezh;
  306. treap* verch=iskatotrezok(c,d,korendereva);
  307. treap* znpr=verch;
  308. if (d=(verch->k))
  309.          {//proverka levogo;
  310.          if (c=(verch->n))
  311.          {return(verch);}
  312.          else
  313.               {verchf=iskatotrezok(n1rab-d+1,n1rab-c+1,obratkorendereva);
  314.               verch=verchf;
  315.               //proverka <na> prav;
  316.               if (((verch->pr)->k)==(verch->k))
  317.               {verch=((((verch->pr)->pr)->r)->l);
  318.               promezh=min (((n1rab-c+1)-(verchf->k)),verch);
  319.               return   (minimum (znpr,promezh ));}
  320.               else
  321.               {verch=((verch->pr)->r);
  322.               return(minimum(znpr,min((n1rab-c+1)-(verchf->k),verch)));}
  323.          	   ;}
  324.  
  325.          ;}
  326. else
  327.        {      //proverka <na> prav;
  328.               if (((verch->pr)->k)==(verch->k))
  329.               {verch=((((verch->pr)->pr)->r)->l);
  330.               prmin=minimum(znpr,min((n1rab-d+1)-(verchf->k),verch));}
  331.               else
  332.               {verch=((verch->pr)->r);
  333.               prmin=minimum(znpr, min((n1rab-d+1)-(verchf->k),verch));}
  334.  
  335.  
  336.  
  337.               {//proverka levogo;
  338.          if (c=(verch->n))
  339.               {return(prmin);}
  340.          else
  341.               {verchf=iskatotrezok(n1rab-d+1,n1rab-c+1,obratkorendereva);
  342.               verch=verchf;
  343.               //proverka <na> prav;
  344.               if (((verch->pr)->k)==(verch->k))
  345.               {verch=((((verch->pr)->pr)->r)->l);
  346.               return(minimum(prmin,min((n1rab-c+1)-(verchf->k),verch)));}
  347.               else
  348.               {verch=((verch->pr)->r);
  349.               return(minimum(prmin,min((n1rab-c+1)-(verchf->k),verch)));}
  350.          	   ;}
  351.  
  352.          ;}  
  353.  
  354.  
  355.         ;}
  356.  
  357.  
  358.  
  359.  
  360. ;}
  361.  
  362.  
  363.  
  364.  
  365.  
  366. long long i2, m2, n2, a2, b2;
  367. int main()
  368.  
  369. {
  370.  /*	freopen("rsq.in", "r", stdin);
  371. 	freopen("rsq.out", "w", stdout);*/
  372. 	scanf("%d%d", &n2, &m2);
  373. 	postroenie_dereva(n2);
  374.             obratpostroenie_dereva(n2);
  375.  
  376.  
  377.            printtt(korendereva);
  378.  
  379. 	 printf("%lld \n",(iskatotrezok(5,7,(korendereva->r)))->minpl);
  380.  
  381. }
  382.  
Runtime error #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
6 3
1 8 4 5 3 7
stdout
copy 
Standard output is empty
https://ideone.com/a3xAFy
language:
C++ (gcc 8.3)
created:
6 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!