| Problem | Verdict | Lang | Time | Best | Rank | Submit Time |
|---|---|---|---|---|---|---|
π |  | discuss11235 - | Accepted | C++11 | 0.220 | 0.010 | 1841 | 7 mins ago |
Suggest:
- Lv0: Use RMQ for with value is frequence of a[i]
- Lv1: https://algorithmist.com/wiki/UVa_11235
- Lv2: https://niceproblems.blogspot.com/2012/05/uva-11235-frequent-values.html
* I was able solve after read lv2, i think you can too :)
* I was able solve after read lv2, i think you can too :)
#include<bits/stdc++.h>
#define FOR(i, a, b) for(int i=a; i<=b; i++)
using namespace std;
const int N=1000111;
const int oo=1000111000;
int n,m;
int A, B;
int a[N], st[4*N];
unordered_map<int, int> cnt, start;
void build(int id, int l, int r){
if (l==r){
st[id]= cnt[ a[l] ];
return;
}
int mid=(l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id]=max(st[id*2], st[id*2+1]);
}
int getMAX(int id, int l, int r){
if (r < A || l > B) return -oo;
if (A <= l && r <= B) return st[id];
int mid=(l+r)/2;
return max( getMAX(id*2, l, mid) ,getMAX(id*2+1, mid+1, r) );
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
while(cin >> n && n){
cin >> m;
cnt.clear();
FOR(i, 1, n){
cin >> a[i];
cnt[a[i]]++;
if (cnt[a[i]]==1) start[a[i]]= i;
}
build(1, 1, n);
FOR(i, 1, m){
cin >> A >> B;
if (a[A] == a[B]) cout<<B-A+1<<"\n";
else{
int resL = start[ a[A] ] + cnt[ a[A] ] - A;
int resR = B - start[ a[B] ] + 1;
int ans= max(resL, resR);
A= start[ a[ A ] ] + cnt[ a[ A ] ] ;
B = start[ a[ B ] ] - 1;
cout<<max(ans, getMAX(1, 1, n))<<"\n";
}
}
}
}
No comments:
Post a Comment