fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. template<class S, class T> inline S min_L(S a,T b){
  5.   return a<=b?a:b;
  6. }
  7. template<class S, class T> inline S divup_L(S a, T b){
  8.   return (a+b-1)/b;
  9. }
  10. #define main dummy_main
  11. int main(){
  12.   return 0;
  13. }
  14. #undef main
  15. int gcnt[20001];
  16. class MajorityChecker{
  17.   int B, M, N, mval[100];
  18.   map<int,int> mp[100];
  19.   vector<int> A;
  20.   public:
  21.   MajorityChecker(vector<int>& arr){
  22.     int a, b, i, j, k, mxind, mxval;
  23.     A = arr;
  24.     N = A.size();
  25.     M = 300;
  26.     B =divup_L(N,M);
  27.     for(i=0;i<(20001);i++){
  28.       gcnt[i] = 0;
  29.     }
  30.     for(k=0;k<(B);k++){
  31.       a = M*k;
  32.       b =min_L(M*(k+1), N);
  33.       mxval = 0;
  34.       for(i=(a);i<(b);i++){
  35.         gcnt[A[i]]++;
  36.         if(mxval < gcnt[A[i]]){
  37.           mxval = gcnt[A[i]];
  38.           mxind = A[i];
  39.         }
  40.       }
  41.       mval[k] = mxind;
  42.       for(i=(a);i<(b);i++){
  43.         mp[k][A[i]] = gcnt[A[i]];
  44.       }
  45.       for(i=(a);i<(b);i++){
  46.         gcnt[A[i]]--;
  47.       }
  48.     }
  49.   }
  50.   int query(int a, int b, int t){
  51.     int aa, bb, cnt, i, ii, val, x;
  52.     vector<int> koho;
  53.     b++;
  54.     if(b-a < 1000){
  55.       cnt = 0;
  56.       for(i=(a);i<(b);i++){
  57.         if(cnt==0){
  58.           val = A[i];
  59.           cnt++;
  60.         }
  61.         else if(val==A[i]){
  62.           cnt++;
  63.         }
  64.         else{
  65.           cnt--;
  66.         }
  67.       }
  68.       if(cnt==0){
  69.         return -1;
  70.       }
  71.       cnt = 0;
  72.       for(i=(a);i<(b);i++){
  73.         if(val==A[i]){
  74.           cnt++;
  75.         }
  76.       }
  77.       if(cnt >= t){
  78.         return val;
  79.       }
  80.       return -1;
  81.     }
  82.     aa = (divup_L(a,M)) * M;
  83.     bb = (b / M) * M;
  84.     if(a != aa){
  85.       i = query(a,aa-1,0);
  86.       if(i>=0){
  87.         koho.push_back(i);
  88.       }
  89.     }
  90.     if(b != bb){
  91.       i = query(bb,b-1,0);
  92.       if(i>=0){
  93.         koho.push_back(i);
  94.       }
  95.     }
  96.     for(i=(aa/M);i<(bb/M);i++){
  97.       koho.push_back(mval[i]);
  98.     }
  99.     sort(koho.begin(), koho.end());
  100.     for(ii=0;ii<(koho.size());ii++){
  101.       if(ii>0 && koho[ii]==koho[ii-1]){
  102.         continue;
  103.       }
  104.       x = koho[ii];
  105.       cnt = 0;
  106.       for(i=(a);i<(aa);i++){
  107.         if(A[i]==x){
  108.           cnt++;
  109.         }
  110.       }
  111.       for(i=(aa/M);i<(bb/M);i++){
  112.         if(mp[i].count(x)){
  113.           cnt += mp[i][x];
  114.         }
  115.       }
  116.       for(i=(bb);i<(b);i++){
  117.         if(A[i]==x){
  118.           cnt++;
  119.         }
  120.       }
  121.       if(cnt >= t){
  122.         return x;
  123.       }
  124.     }
  125.     return -1;
  126.   }
  127. }
  128. ;
  129. // cLay varsion 20190818-1
  130.  
  131. // --- original code ---
  132. // #define main dummy_main
  133. // {}
  134. // #undef main
  135. // 
  136. // int gcnt[20001];
  137. // 
  138. // class MajorityChecker {
  139. // public:
  140. //   int N;
  141. //   vector<int> A;
  142. // 
  143. //   int M, B;
  144. //   int mval[100];
  145. //   map<int,int> mp[100];
  146. //   
  147. //   MajorityChecker(vector<int>& arr) {
  148. //     int i, j, k, a, b;
  149. //     int mxind, mxval;
  150. //     
  151. //     A = arr;
  152. //     N = A.size();
  153. // 
  154. //     M = 300;
  155. //     B = N /+ M;
  156. // 
  157. //     rep(i,20001) gcnt[i] = 0;
  158. // 
  159. //     rep(k,B){
  160. //       a = M*k;
  161. //       b = min(M*(k+1), N);
  162. // 
  163. //       mxval = 0;
  164. //       rep(i,a,b){
  165. //         gcnt[A[i]]++;
  166. //         if(mxval < gcnt[A[i]]){
  167. //           mxval = gcnt[A[i]];
  168. //           mxind = A[i];
  169. //         }
  170. //       }
  171. //       mval[k] = mxind;
  172. //       rep(i,a,b) mp[k][A[i]] = gcnt[A[i]];
  173. //       rep(i,a,b) gcnt[A[i]]--;
  174. //     }
  175. //   }
  176. //   
  177. //   int query(int a, int b, int t) {
  178. //     int i, ii, x, aa, bb;
  179. //     int val, cnt;
  180. //     vector<int> koho;
  181. // 
  182. //     b++;
  183. // 
  184. //     if(b-a < 1000){
  185. // 
  186. //       cnt = 0;
  187. //       rep(i,a,b){
  188. //         if(cnt==0){
  189. //           val = A[i];
  190. //           cnt++;
  191. //         } else if(val==A[i]){
  192. //           cnt++;
  193. //         } else {
  194. //           cnt--;
  195. //         }
  196. //       }
  197. //       if(cnt==0) return -1;
  198. //       
  199. //       cnt = 0;
  200. //       rep(i,a,b) if(val==A[i]) cnt++;
  201. //       if(cnt >= t) return val;
  202. //       return -1;
  203. //       
  204. //     }
  205. // 
  206. //     aa = (a /+ M) * M;
  207. //     bb = (b / M) * M;
  208. // 
  209. //     if(a != aa){
  210. //       i = query(a,aa-1,0);
  211. //       if(i>=0) koho.push_back(i);
  212. //     }
  213. //     if(b != bb){
  214. //       i = query(bb,b-1,0);
  215. //       if(i>=0) koho.push_back(i);
  216. //     }
  217. //     rep(i,aa/M,bb/M) koho.push_back(mval[i]);
  218. //     sort(koho.begin(), koho.end());
  219. // 
  220. //     rep(ii,koho.size()){
  221. //       if(ii>0 && koho[ii]==koho[ii-1]) continue;
  222. //       x = koho[ii];
  223. // 
  224. //       cnt = 0;
  225. //       rep(i,a,aa) if(A[i]==x) cnt++;
  226. //       rep(i,aa/M,bb/M) if(mp[i].count(x)) cnt += mp[i][x];
  227. //       rep(i,bb,b) if(A[i]==x) cnt++;
  228. // 
  229. //       if(cnt >= t) return x;
  230. //     }
  231. // 
  232. //     return -1;
  233. //   }
  234. // };
  235.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/bTohAo
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!