这一题是个奇葩的电梯...它的策略是每秒贪心,

想要电梯向上的人如果>=向下的,那么就向上好了

不然就向下好了

原题地址:http://codeforces.com/contest/257/problem/E

这个题的做法应该是利用好m<=100000的条件,弄个线段树来搞

val[x]表示要求到x的人数

可以写二分来求前驱后继

也可以在线段树上走来求

还可以像我省选二轮一样写颗平衡树

于是..没然后了...注意下细节就可以

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct thing
{
    long long t;
    int from;
    int to;
    int id;
    void read()
    {
        int x;
        scanf("%d%d%d",&x,&from,&to);
        from--;
        to--;
        t=x;
    }
    friend bool operator < (const thing &a,const thing &b)
    {
        return a.t<b.t;
    }
};
thing a[100005];
int val[1<<18];
int leaf[1<<18];
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        val[num]=0;
        leaf[num]=l;
        return;
    }
    int mid=(l+r)>>1;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    leaf[num]=-1;
}
void change(int num,int l,int r,int t,int k)
{
    val[num]+=k;
    if (l==r-1)
    {
        return;
    }
    int mid=(l+r)>>1;
    if (t<mid)
    {
        change(num*2+1,l,mid,t,k);
    }
    else
    {
        change(num*2+2,mid,r,t,k);
    }
}
int query_loc(int num,int l,int r,int k)
{
    if (l==r-1)
    {
        return num;
    }
    int mid=(l+r)>>1;
    if (k<mid)
    {
        return query_loc(num*2+1,l,mid,k);
    }
    else
    {
        return query_loc(num*2+2,mid,r,k);
    }
}
int query(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)>>1;
    int val=0;
    if (l0<mid) val+=query(num*2+1,l,mid,l0,r0);
    if (mid<r0) val+=query(num*2+2,mid,r,l0,r0);
    return val;
}
int find_left(int loc)
{
    if (val[loc]>=1) return leaf[loc];
    for (;;)
    {
        if (!(loc&1))
        {
            if (val[loc]!=val[(loc-1)>>1]) break;
        }
        loc=(loc-1)>>1;
    }
    loc=(loc-1)>>1;
    loc=loc*2+1;
    for (;;)
    {
        if (leaf[loc]!=-1)
        {
            break;
        }
        if (val[loc*2+2]!=0)
        {
            loc=loc*2+2;
        }
        else
        {
            loc=loc*2+1;
        }
    }
    return leaf[loc];
}
int find_right(int loc)
{
    if (val[loc]>=1) return leaf[loc];
    for (;;)
    {
        if (loc&1)
        {
            if (val[loc]!=val[(loc-1)>>1]) break;
        }
        loc=(loc-1)>>1;
    }
    loc=(loc-1)>>1;
    loc=loc*2+2;
    for (;;)
    {
        if (leaf[loc]!=-1)
        {
            break;
        }
        if (val[loc*2+1]!=0)
        {
            loc=loc*2+1;
        }
        else
        {
            loc=loc*2+2;
        }
    }
    return leaf[loc];
}
long long ans[100005];
int state[100005];
struct node
{
    int y;
    node * next;
};
node * new_node()
{
    static node a[300005];
    static int top=0;
    return &a[top++];
};
node * li[100005];
void inserts(int x,int y)
{
    node * t=new_node();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        a[i].read();
        a[i].id=i;
        state[i]=0;
    }
    sort(a,a+n);
    long long now_time=a[0].t;
    build_tree(0,0,m);
    a[n].t=999999999999999999ll;
    change(0,0,m,a[0].from,1);
    inserts(a[0].from,0);
    int floor=0;
    for (i=0;i<n;)
    {
        if (now_time==a[i+1].t)
        {
            i++;
            change(0,0,m,a[i].from,1);
            inserts(a[i].from,i);
            continue;
        }
        int down=query(0,0,m,0,floor+1);
        int up=query(0,0,m,floor,m);
        if ((up==0)&&(down==0))
        {
            now_time=a[i+1].t;
            continue;
        }
        if (up<down)
        {
            int t=find_left(query_loc(0,0,m,floor));
            if (floor-t+now_time>=a[i+1].t)
            {
                floor-=(a[i+1].t-now_time);
                now_time=a[i+1].t;
                continue;
            }
            else
            {
                now_time+=floor-t;
                floor=t;
                for (;li[t]!=0;li[t]=li[t]->next)
                {
                    if (state[li[t]->y]==0)
                    {
                        state[li[t]->y]=1;
                        change(0,0,m,floor,-1);
                        change(0,0,m,a[li[t]->y].to,1);
                        inserts(a[li[t]->y].to,li[t]->y);
                    }
                    else if (state[li[t]->y]==1)
                    {
                        change(0,0,m,floor,-1);
                        ans[a[li[t]->y].id]=now_time;
                        state[li[t]->y]=2;
                    }
                }
            }
        }
        else
        {
            int t=find_right(query_loc(0,0,m,floor));
            if (t-floor+now_time>=a[i+1].t)
            {
                floor+=(a[i+1].t-now_time);
                now_time=a[i+1].t;
                continue;
            }
            else
            {
                now_time+=t-floor;
                floor=t;
                for (;li[t]!=0;li[t]=li[t]->next)
                {
                    if (state[li[t]->y]==0)
                    {
                        state[li[t]->y]=1;
                        change(0,0,m,floor,-1);
                        change(0,0,m,a[li[t]->y].to,1);
                        inserts(a[li[t]->y].to,li[t]->y);
                    }
                    else if (state[li[t]->y]==1)
                    {
                        change(0,0,m,floor,-1);
                        ans[a[li[t]->y].id]=now_time;
                        state[li[t]->y]=2;
                    }
                }
            }
        }
    }
    ios::sync_with_stdio(false);
    for (i=0;i<n;i++)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}