daily pastebin goal
41%
SHARE
TWEET

UVA 11235 TLE

sabertooth09 May 16th, 2018 114 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. //#include<unordered_map>
  3. typedef long long ll;
  4. #define PQ priority_queue
  5. #define ii int,int
  6. using namespace std;
  7. const int N=100000;
  8. struct node
  9. {
  10.     int cnt,val;
  11.     map<ii>mp;
  12.     node()
  13.     {
  14.         mp.clear();
  15.         cnt=0,val=0;
  16.     }
  17. };
  18. map<ii>ans;
  19. node tree[4*N+2];
  20. int ara[N+2];
  21. void clr()
  22. {
  23.     memset(ara,0,sizeof ara);
  24.     ans.clear();
  25.     for(int i=0; i<=N; i++)
  26.     {
  27.         tree[i].mp.clear();
  28.         tree[i].cnt=0,tree[i].val=0;
  29.     }
  30. }
  31. pair<ii>get_max(map<ii>mp)
  32. {
  33.     pair<ii>ans= {0,0};
  34.     for(map<ii>::iterator itr=mp.begin(); itr!=mp.end(); itr++)
  35.     {
  36.         if(itr->second>ans.second)
  37.         {
  38.             ans= {itr->first,itr->second};
  39.         }
  40.     }
  41.     return ans;
  42. }
  43. map<ii> operator + (map<ii>mp1,map<ii>mp2)
  44. {
  45.     map<ii>::iterator itr;
  46.     for(itr=mp1.begin(); itr!=mp1.end(); itr++)
  47.         mp2[itr->first]+=itr->second;
  48.     return mp2;
  49. }
  50. void build(int nx,int st,int en)
  51. {
  52.     tree[nx].mp.clear();
  53.     if(st==en)
  54.     {
  55.         tree[nx].mp[ara[st]]++;
  56.         tree[nx].cnt=tree[nx].mp[ara[st]];
  57.         tree[nx].val=ara[st];
  58.         return;
  59.     }
  60.     int lt=nx*2;
  61.     int rg=nx*2+1;
  62.     int mid=(st+en)/2;
  63.     build(lt,st,mid);
  64.     build(rg,mid+1,en);
  65.     tree[nx].mp=tree[lt].mp+tree[rg].mp;
  66.     pair<ii>itr=get_max(tree[nx].mp);
  67.     tree[nx].cnt=itr.second;
  68.     tree[nx].val=itr.first;
  69. }
  70. void query(int nx,int st,int en,int lt,int rg)
  71. {
  72.     if(lt>en or rg<st)
  73.         return;
  74.     if(st>=lt and en<=rg)
  75.     {
  76.         ans=ans+tree[nx].mp;
  77.         return;
  78.     }
  79.     int L=nx*2;
  80.     int R=nx*2+1;
  81.     int mid=(st+en)/2;
  82.     query(L,st,mid,lt,rg);
  83.     query(R,mid+1,en,lt,rg);
  84. }
  85. int main()
  86. {
  87.     freopen("input.txt","r",stdin);
  88.     freopen("output.txt","w",stdout);
  89.     int n,q;
  90.     while(scanf("%d",&n)==1 and n)
  91.     {
  92.         //clr();
  93.         scanf("%d",&q);
  94.         for(int i=1; i<=n; i++)
  95.             scanf("%d",&ara[i]);
  96.         build(1,1,n);
  97.         int l,r;
  98.         while(q--)
  99.         {
  100.             scanf("%d %d",&l,&r);
  101.             ans.clear();
  102.             query(1,1,n,l,r);
  103.             pair<ii>itr=get_max(ans);
  104.             printf("%d\n",itr.second);
  105.         }
  106.     }
  107. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top