记录编号 |
308751 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NEERC 2004] K小数 |
最终得分 |
100 |
用户昵称 |
YGOI_真神名曰驴蛋蛋 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.025 s |
提交时间 |
2016-09-18 17:09:58 |
内存使用 |
21.28 MiB |
显示代码纯文本
#include<cstdio>
#include<algorithm>
//#include <windows.h>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Betin freopen("kthnumber.in","r",stdin);freopen("kthnumber.out","w",stdout);
#define Begin Betin;chul();Cu;
using namespace std;
typedef long long ll;
const int maxn=1010;
const ll INF=~0ULL>>2;
ll a[maxn*maxn],tub[maxn*maxn],tsd[maxn*maxn];
ll n,s,t,k;
ll ntub,b;
ll getsqrt(ll x){
ll l=1,r=x;
ll mid,ans=l;
while(l<r){
mid=(l+r)>>1;
if(mid*mid<x){
ans=mid;
l=mid+1;
}
else r=mid;
}
return ans;
}
int JUDGE(ll x){
ll l=s,r=t,cnt=0;
while(((l)%b)&&l<=r){
if(a[l]<x){
cnt++;
}
//printf("l:::%d\n",l+1);
l++;
}
while(((r+1)%b)&&l<=r){
if(a[r]<x){
cnt++;
}
//printf("r:::%lld\n",r+1);
r--;
}//printf("-->%d ",cnt);
if(l<r)
for(ll i=l/b;i<=r/b;i++){
ll poi=lower_bound(tub+i*b,tub+i*b+b,x)-tub;
// printf("poi:::%lld\n",poi);
cnt+=(poi-i*b);
}
return cnt;
}
void chul(){
ll m;scanf("%lld%lld",&n,&m);
ntub=getsqrt(n);
b=n/ntub;
for(ll i=0;i<n;i++){
scanf("%lld",&a[i]);
tub[i]=a[i];
tsd[i+1]=a[i];
}
for(ll i=0;i<ntub;i++){
sort(tub+i*b,tub+i*b+b);
}
sort(tsd+1,tsd+1+n);
for(ll i=1;i<=m;i++){
scanf("%lld%lld%lld",&s,&t,&k);
ll ans=1,mid;
s--;t--;
if(s==t){
printf("%lld\n",a[s]);
continue;
}
ll l=-INF,r=INF;
while(l<=r){
mid=(l+r)>>1LL;
int cnt=JUDGE(mid);
//printf("HERE");
//if(s==0&&t==1&&k==2)printf("l:%lld mid:%lld(%d) r:%lld \n",l,mid,cnt,r), Sleep(50);
if(cnt<k)ans=mid,l=mid+1;
else r=mid-1;
}
// if(JUDGE(tsd[ans-1]))ans=ans-1;
printf("%lld\n",ans);
}
//while(getchar()!='e');
}
int main(){
Begin;
}