ACM-ICPC 2018 南京赛区网络预赛 G. Lpl and Energy-saving Lamps (弱线段树)

线段树节点维护区间最小值,查找时优先从左侧的区间寻找.

每一次循环都在树中不停寻找第一个小于等于当前持有数的值,然后抹去,直到找不到为止.

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define lson rt<<1

#define rson rt<<1|1

#define Lson l,m,lson

#define Rson m+1,r,rson

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

const int maxn=1e5+5;

int val[maxn];

struct Node{

    int num;

}tree[maxn<<2];

int n;

void pushup(int rt)

{

    tree[rt].num = min(tree[lson].num,tree[rson].num);

}

void build(int l=1,int r=n,int rt=1)

{

    if(l==r){

        tree[rt].num = val[l];

        return ;

    }

    int m = (l+r)>>1;

    build(Lson);

    build(Rson);

    pushup(rt);

}

bool flag;

int query(int val,int l=1,int r=n,int rt=1)

{

    int res=-1,m = (l+r)>>1;

    if(tree[rt].num<=val){

        if(l==r){

            int tmp = tree[rt].num;

            tree[rt].num = INF;

            return  tmp;

        }

        res = query(val,Lson);

        if(res!=-1) {

            pushup(rt);

            return res;

        }

        res = query(val,Rson);

        if(res!=-1){

            pushup(rt);

            return res;

        }

    }

    return -1;

}

int ans1[maxn];

int ans2[maxn];

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int m,q;

    while(scanf("%d %d",&n,&m)==2){

        for(int i=1;i<=n;++i){

            scanf("%d",&val[i]);

        }

        build();

        flag = false;

        int sum = 0,tot=0;

        for(int i=1;i<=100000;++i){

            //cout<<tree[1].num<<endl;

            if(tree[1].num ==INF) flag = true;

            if(!flag) {

                sum += m;

                int tmp = query(sum);

                while(tmp!=-1){

                    sum-=tmp;

                    tot++;

                    tmp = query(sum);

                }

            }

            ans1[i] = tot;

            ans2[i] = sum;

        }

        int id;

        scanf("%d",&q);

        for(int i=1;i<=q;++i){

            scanf("%d",&id);

            printf("%d %d\n",ans1[id],ans2[id]);

        }

    }

    return 0;

}

巴特西

ACM-ICPC 2018 南京赛区网络预赛 G. Lpl and Energy-saving Lamps (弱线段树)

最新文章

热门文章