fork(1) download
  1. #include<cstring>
  2. #include<cstdlib>
  3. //#include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6. struct Node
  7. {
  8. pair<int,int> v;
  9. int ansv;
  10. int ansi;
  11. int sz;
  12. Node *l;
  13. Node *r;
  14. Node *p;
  15. };
  16. Node *root;
  17. void UpdateSize(Node *P)
  18. {
  19. P->sz=1;
  20. if(P->l) P->sz+=P->l->sz;
  21. if(P->r) P->sz+=P->r->sz;
  22.  
  23. }
  24. void RightRotate(Node *P)
  25. {
  26. Node *T=P->l;
  27. Node *B=T->r;
  28. Node *D=P->p;
  29. if(D)
  30. {
  31. if(D->l==P) D->l=T;
  32. else D->r=T;
  33. }
  34. if(B)
  35. B->p=P;
  36.  
  37. P->p=T;
  38. P->l=B;
  39. UpdateSize(P);
  40.  
  41. T->r=P;
  42. T->p=D;
  43. UpdateSize(T);
  44. }
  45. void LeftRotate(Node *P)
  46. {
  47. Node *T=P->r;
  48. Node *B=T->l;
  49. Node *D=P->p;
  50. if(D)
  51. {
  52. if(D->l==P) D->l=T;
  53. else D->r=T;
  54. }
  55. if(B)
  56. B->p=P;
  57.  
  58. P->p=T;
  59. P->r=B;
  60. UpdateSize(P);
  61.  
  62. T->l=P;
  63. T->p=D;
  64. UpdateSize(T);
  65. }
  66. void Splay(Node *P)
  67. {
  68. while(P->p)
  69. {
  70. Node* PP=P->p;
  71. Node* PPP=PP->p;
  72. if(!PPP)
  73. {
  74. if(PP->l==P) RightRotate(PP);
  75. else LeftRotate(PP);
  76. break;
  77. }
  78. if(PPP->l==PP)
  79. {
  80. if(PP->l==P)
  81. {
  82. RightRotate(PPP);
  83. RightRotate(PP);
  84. }
  85. else
  86. {
  87. LeftRotate(PP);
  88. RightRotate(PPP);
  89. }
  90. }
  91. else
  92. {
  93. if(PP->l==P)
  94. {
  95. RightRotate(PP);
  96. LeftRotate(PPP);
  97. }
  98. else
  99. {
  100. LeftRotate(PPP);
  101. LeftRotate(PP);
  102. }
  103. }
  104. }
  105. root=P;
  106. }
  107. void Insert(pair<int, int> v,int ansv,int ansi)
  108. {
  109. Node *T=root;
  110. if(!T)
  111. {
  112. root=(Node*) malloc(sizeof(Node));
  113. root->l=NULL;
  114. root->r=NULL;
  115. root->p=NULL;
  116. root->v=v;
  117. root->sz=1;
  118. root->ansv=ansv;
  119. root->ansi=ansi;
  120. return;
  121. }
  122. while(T)
  123. {
  124. if(v < (T->v) )
  125. {
  126. if(T->l)
  127. {
  128. T=T->l;
  129. continue;
  130. }
  131. else
  132. {
  133. T->l=(Node *)malloc(sizeof(Node));
  134. T->l->l=NULL;
  135. T->l->r=NULL;
  136. T->l->p=T;
  137. T->l->v=v;
  138. T->l->ansv=ansv;
  139. T->l->ansi=ansi;
  140. T->l->sz=1;
  141. T=T->l;
  142. break;
  143. }
  144. }
  145. else
  146. {
  147. if(T->r)
  148. {
  149. T=T->r;
  150. continue;
  151. }
  152. else
  153. {
  154. T->r=(Node *)malloc(sizeof(Node));
  155. T->r->l=NULL;
  156. T->r->r=NULL;
  157. T->r->p=T;
  158. T->r->v=v;
  159. T->r->ansv=ansv;
  160. T->r->ansi=ansi;
  161. T->r->sz=1;
  162. T=T->r;
  163. break;
  164. }
  165. }
  166. }
  167. Node* tosplay=T;
  168. while(T)
  169. {
  170. UpdateSize(T);
  171. T=T->p;
  172. }
  173. Splay(tosplay);
  174. }
  175.  
  176. Node* Find(pair<int,int> v)
  177. {
  178. Node *T=root;
  179. while(T)
  180. {
  181. if(v==(T->v))
  182. {
  183. Splay(T);
  184. return T;
  185. }
  186. if(v< (T->v))
  187. {
  188. if(T->l)
  189. {
  190. T=T->l;
  191. }
  192. else
  193. {
  194. Splay(T);
  195. return NULL;
  196. }
  197. }
  198. else
  199. {
  200. if(T->r)
  201. {
  202. T=T->r;
  203. }
  204. else
  205. {
  206. Splay(T);
  207. return NULL;
  208. }
  209. }
  210. }
  211. return NULL;
  212. }
  213.  
  214. void Erase(Node *T)
  215. {
  216. Splay(T);
  217.  
  218. if(T->l)
  219. {
  220. root=T->l;
  221. Node *x=root;
  222. while(x->r) x=x->r;
  223. x->r=T->r;
  224. if(T->r) T->r->p=x;
  225. while(x->p)
  226. {
  227. UpdateSize(x);
  228. x=x->p;
  229. }
  230. }
  231. else
  232. root=T->r;
  233. free(T);
  234. if(root)root->p=NULL;
  235. }
  236.  
  237. Node* findKth(Node *T,int K)
  238. {
  239. int sz=0;
  240. if(T->l) sz=T->l->sz;
  241. if(sz==K) return T;
  242. if(sz>K)
  243. return findKth(T->l,K);
  244. else
  245. return findKth(T->r,K-sz-1);
  246. }
  247. Node* findKth(int K)
  248. {
  249. Node* Kth=findKth(root,K);
  250. Splay(Kth);
  251. return Kth;
  252. }
  253. int R;
  254. const int MAXN=131072;
  255. int idx[MAXN*2];
  256. int getmax(int l,int r)
  257. {
  258. l+=MAXN;
  259. r+=MAXN;
  260. int ans=0;
  261. while(l<=r)
  262. {
  263. if(l%2==1)
  264. ans=max(ans,idx[l++]);
  265. if(r%2==0)
  266. ans=max(ans,idx[r--]);
  267. l/=2;
  268. r/=2;
  269. }
  270. return ans;
  271. }
  272. void Query(int A,int B) //from Ath Node to Bth Node (0-based)
  273. {
  274. int findcount=B-A+1;
  275. Node *Ath=findKth(A);
  276. Node *Bth=findKth(B);
  277. //printf("%d %d %d %d\n",A,B,(Ath->v).first,(Bth->v).first);
  278. int ansv=-1;
  279. int ansi=-1;
  280. pair<int,int> v=make_pair((Ath->v).first,(Bth->v).second);
  281. //printf("%d\n",root->sz);
  282. for(int i=0;i<findcount;i++)
  283. {
  284. // printf("%d %d\n",root->sz,A);
  285. Node *Ath=findKth(A);
  286. if(ansv < (Ath->ansv))
  287. {
  288. ansv=Ath->ansv;
  289. ansi=Ath->ansi;
  290. }
  291. //printf("%d\n",root->sz);
  292. Erase(Ath);
  293. }
  294. //puts("ok");
  295. int ans=getmax(v.first,v.second-1);
  296.  
  297. if(ans<R) ansv++;
  298. Insert(v,ansv,ansi);
  299. }
  300.  
  301.  
  302. int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
  303. {
  304. ::R=R;
  305. for(int i=0;i<N;i++)
  306. Insert(make_pair(i,i),0,i);
  307. for(int i=0;i<N-1;i++)
  308. idx[MAXN+i]=K[i];
  309. for(int i=MAXN-1;i>=1;i--)
  310. idx[i]=max(idx[2*i],idx[2*i+1]);
  311. for(int i=0;i<C;i++)
  312. Query(S[i],E[i]);
  313. return root->ansi;
  314. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
Standard output is empty