队列:二分+读入优化+优化

问题 B: 队列
时间限制: 1 Sec 内存限制: 20 MB
提交: 271 解决: 22
题目描述
NQI终于出分了,一直忐忑不安的小H飞奔到公示栏前,小H却发现老师公布了两个排行榜,分别是NQI正式选手和NQI邀请赛选手分别的排名。但小H当然想知道所有人在一起的排名啦。所以他准备将两个榜单和在一起排名。
由于NQI的特殊性,我们可以认为所有的人成绩都为正整数,并且NQI正式选手和NQI邀请赛选手都为n个人。它的成绩也与众不同,成绩的数值越小,排名就越靠前,即排名按成绩的数值从小到大排序。现在小H想知道对于一些排名对应的分数是多少,这样他好对大家的水平有一些了解。

输入格式
第1行,两个正整数n,m,分别表示人数与询问次数
第2,3行,每行n个由小到大排列的正整数,分别表示正式选手与邀请赛选手成绩
接下来m行,每行一个正整数x,表示询问排名(数据保证合法)
由于本题强制在线,记lastans为上一次的回答,初始lastans=0,x=x^lastans%(2*n)+1
输出格式
共m行,每行一个整数,表示排名对应分数
输入样例
3 2
1 2 3
2 3 4
5
3
输出样例
4
2
数据范围
20 % n<=1e5
40 % n<=1e6
100 % n<=2e6,m<=1e4 所有数据保证在int范围内

由于输入数据较大,本题附带文件已经将输入部分写好。

#include <cstdio>
#include <algorithm>
#include <iostream>
#define N 2000005
#define INF 23333333
using namespace std;
int a[N],b[N],n,m;
int lastans=0;
char xB[1<<15],*xS=xB,*xTT=xB;
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
#define isd(c) (c>='0'&&c<='9')
inline int read(){
    char xchh;
    int xaa;
    while(xchh=getc(),!isd(xchh));(xaa=xchh-'0');
    while(xchh=getc(),isd(xchh))xaa=xaa*10+xchh-'0';return xaa;
}
inline void init(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
}
inline int solve(int lc){
    int l=0; 
    int r=lc;
    if(lc>n) l=lc-n,r=n;
    int mid;
    while(l<=r){
        mid=(l+r)>>1;
        int ta=a[mid];
        int tb=b[lc-mid];
        if(ta<tb){
            if(a[mid+1]>tb) return tb;
            else l=mid+1;
        }
        else {
            if(b[lc-mid+1]>ta) return ta;
            else r=mid-1;
        }
    }   
    return max(a[mid],b[lc-mid]);
}
int main(){
    init();
    a[n+1]=b[n+1]=INF;
    lastans=0;
    int modd=2*n;
    int q;
    for(int i=1;i<=m;i++){
        q=read();
        q^=lastans;
        q=q%(2*n)+1;
        lastans=solve(q);
        printf("%d\n",lastans);
    }
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-27 14:49
韶关学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议