首页 > 其他 > 详细

P1311 选择客栈

时间:2018-09-23 11:11:02      阅读:147      评论:0      收藏:0      [点我收藏+]

P1311 选择客栈

RMQ+二分(当然这并不是正解)

对于每一个客栈,二分满足条件的范围,在RMQ上查询。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cctype>
using namespace std;
template <typename T> inline T min(T &a,T &b) {return a<b ? a:b;}
template <typename T> inline void read(T &x){
    char c=getchar(); x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int n,k,p,mnd[18][200002],log[200002]; long long ans;
vector <int> g[52];
inline int query(int l,int r){
    int k=log[r-l+1];
    return min(mnd[k][l],mnd[k][r-(1<<k)+1]);
}
int main(){
    read(n); read(k); read(p); int q; log[0]=-1;
    for(int i=1;i<=n;++i){
        read(q); read(mnd[0][i]);
        g[q].push_back(i);
        log[i]=log[i>>1]+1;
    }
    for(int i=1;(1<<i)<=n;++i)
        for(int j=1;j+(1<<(i-1))<=n;++j)
            mnd[i][j]=min(mnd[i-1][j],mnd[i-1][j+(1<<(i-1))]);
    for(int i=0;i<k;++i)
        for(int j=0;j<g[i].size()-1;++j){
            if(query(g[i][j],g[i][g[i].size()-1])>p) break; //已经无法满足条件就跳出
            int l=j+1,r=g[i].size()-1,mid;
            while(l<r){ //二分确定范围
                mid=l+((r-l)>>1);
                if(query(g[i][j],g[i][mid])>p) l=mid+1;
                else r=mid;
            }ans+=g[i].size()-l;
        }
    printf("%lld",ans);
    return 0;
}

 

P1311 选择客栈

原文:https://www.cnblogs.com/kafuuchino/p/9692015.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!