记录编号 | 483304 | 评测结果 | AAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [POI 2014] 快递员 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 1.383 s | ||
提交时间 | 2018-01-16 09:43:41 | 内存使用 | 116.70 MiB | ||
#include<bits/stdc++.h> #define MAXN 500010 #define lc(x) t[x].l #define rc(x) t[x].r namespace IO{ char buf[1<<15],*fs,*ft; inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int qr(){ int x=0,rev=0,ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} return rev?-x:x;} }using namespace IO; using namespace std; struct Note{ int l,r,v; }t[MAXN*20]; int N,M,root[MAXN],tot; void Insert(int p,int l,int r,int &rt,int last){ rt=++tot;t[rt]=t[last];t[rt].v++; if(l==r)return; int mid=l+r>>1; if(p<=mid)Insert(p,l,mid,lc(rt),lc(last)); else Insert(p,mid+1,r,rc(rt),rc(last)); } int Query(int a,int b,int l,int r,int k){ if(l==r)return l; int mid=l+r>>1; if(t[lc(b)].v-t[lc(a)].v>k)return Query(lc(a),lc(b),l,mid,k); else if(t[rc(b)].v-t[rc(a)].v>k)return Query(rc(a),rc(b),mid+1,r,k); else return 0; } int x,y; int main(){ freopen("kur.in","r",stdin); freopen("kur.out","w",stdout); N=qr();M=qr(); for(int i=1;i<=N;i++)x=qr(),Insert(x,1,N,root[i],root[i-1]); for(int i=1;i<=M;i++){ x=qr();y=qr(); printf("%d\n",Query(root[x-1],root[y],1,N,(y-x+1)>>1)); } return 0; }