for this problem: http://www.spoj.pl/problems/PATULJCI/
i have got some idea from this analysis by COCI. http://hsin.hr/coci/archive/2009_2010/contest3_solutions.zip
so far my implementation is with segment tree, then binary search.
here is my implementation which is getting WA:
/* Bismillahir Rahmanir Rahim */
/*Coder: Ahmad Faiyaz*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i,0,a)
#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long
#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))
# define VI vector<int>
# define VS vector<string>
# define VC vector<char>
#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()
#define FORIT(i,m) for(__typeof((m).begin()) i=(m).begin();i!=(m).end();i++)
#define pii pair<int,int>
using namespace std;
#define MAX 300005
struct node{
int number,count;
};
int arr [MAX];
node tree [4*MAX];
vector <int> e [100005];
node combine(node l,node r){
node ret;
if(l.number == r.number){
ret.number=l.number;
ret.count= l.count+r.count;
}
else{
if(l.count > r.count){
ret.number= l.number;
ret.count= l.count-r.count;
}
else{
ret.number= r.number;
ret.count= r.count-l.count;
}
}
return ret;
}
node make (int val,int c){
node ret;
ret.count=c;
ret.number=val;
return ret;
}
void build(int node,int left,int right){
if(left==right){
tree[node]= make(arr[left],1);
return;
}
int mid= (left+right)>>1;
build(2*node,left,mid);
build(2*node+1,mid+1,right);
tree[node]= combine(tree[2*node],tree[2*node+1]);
return;
}
node query(int node,int left,int right,int i,int j){
if(left > j || right <i) return make(-1,-10000);
if(left>= i && right<=j){
return tree[node];
}
int mid= (left+right)/2;
return combine(query(2*node,left,mid,i,j), query(2*node+1,mid+1,right,i,j));
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,q,i,j;
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
e[arr[i]].pb(i);
}
build(1,0,n-1);
scanf("%d",&q);
while(q--){
scanf("%d %d",&i,&j);
node ret= query(1,0,n-1,i-1,j-1);
// cout<<ret.number<<" ";
int cnt= upper_bound(all(e[ret.number]),j-1)-lower_bound(all(e[ret.number]),i-1);
int elem= (j-i+1);
if(2*cnt > elem){
printf("yes %d\n",ret.number);
}
else{
printf("no\n");
}
}
return 0;
}
as far as i can see, i am doing same thing as told in the problem analysis!! but getting WA!! i have done checking with the official judge data, it seems that query function is not giving correct number for some range!! what to do?