Lightoj 1087 Diablo (SQRT decomposition)

http://lightoj.com/volume_showproblem.php?problem=1087

1. 
   
2. #include <bits/stdc++.h>
3. using namespace std;
4. #define MAXN 200005
5. int input[MAXN], SQRSIZE;
6. int arr[MAXN];               // original array
7. int block[500];          // decomposed array
8. int blk_sz, n, q, indx;                      // block size
10. // Time Complexity : O(1)
11. void update(int idx, int val)
12. {
13.     int blockNumber = idx / blk_sz;
14.     block[blockNumber]--;
15.     arr[idx] = val;
16. }
17.  void show(){for(int i = 0; i <indx; i++) cout<<arr[i]<<" ";
18.         cout<<"the array\n";
19.  }
20.  void add(int val)
21. {
22.     int blockNumber = indx / blk_sz;
23.     block[blockNumber]++;
24.     arr[indx] = val;
25.     indx++;
26.     //show();
27. }
28. int query(int ix)
29. {
30.     if(ix>=indx) return -1;
31.     int sum = 0,l = 0, ans = -1;
32.     while (sum+block[l] < ix)
33.     {
34.         sum+= block[l];
35.         l++;
36.     }
37.     int c = l*blk_sz;
38.     l = sum;
39.    
40.     while (c!=indx)
41.     {
42.         if(l == ix&& arr[c]!=-1 ) {ans = arr[c];arr[c] = -1;update(c, -1);return ans;}
43.         if(arr[c]!= -1) l++, c++;
44.         else c++;
45.     }
46.     return -1;
47. }
49. void preprocess(int input[], int n)
50. {
51.     int blk_idx = -1;
52.     indx = n;
53.     for (int i=0; i<n; i++)
54.     {
55.         arr[i] = input[i];
56.         if (i%blk_sz == 0)
57.         {
58.             blk_idx++;
59.         }
60.         block[blk_idx]++;
61.     }
62. }
64. // Driver code
65. int main()
66. {  
67.     int ts;
68.     scanf("%d", &ts);
69.     for(int p = 1; p <=ts; p++){
70.     printf("Case %d:\n", p);
71.     scanf("%d%d", &n, &q);
72.     for(int i = 0; i <n; i++) scanf("%d", &input[i]);
73.     SQRSIZE = n+q;
74.     blk_sz = (int)sqrt(n+q) + 1;
75.     //cout<<"block size"<<blk_sz<<" ";
76.     memset(arr, -1, sizeof(arr));
77.     preprocess(input, n);
78.     //for(int i = 0; i <n; i++)cout<<arr[i]<<" ";
79.     for(int i = 0; i <q; i++){
80.     char ch;
81.     getchar();
82.     scanf("%c", &ch);
83.     if(ch == 'a') {
84.         int id;
85.         scanf("%d", &id);
86.         add(id);
87.     }
88.     else {
89.         int id;
90.         scanf("%d", &id);
91.         int ans = query(id-1);
92.         if(ans  == -1) printf("none\n");
93.         else printf("%d\n", ans);
94.        
95.     }
96.     }
97.     }
98.    
99.     return 0;
100. }
101. //may be a little bug but i can't get it 
102. /*
103. 1 5 8
104. 6 5 3 2 1
105. c 1
106. c 1
107. a 20
108. c 4
109. c 4
110. c 3
111. c 2
112. c 1
114. */