CF1260D A Game with Traps

1978 ワード

http://codeforces.com/problemset/problem/1260/D まず明らかに二分の答えを思いつき、能力値の配列を並べておけばいい.どうやってチェックするか考えます.現在の二分値をwとすると、重み>wのトラップを直接越えられない.すべてのトラップをl昇順に並べます.2つ以上のトラップが重なると,この人がこれらのトラップの最小lから最大rまで直接歩いて最適であることが分かった.証明?ここでは2つの区間が重なる場合のみを示す.2つの区間がそれぞれ[a,b],[c,d]、aがチームをaからdに連れて行きたいと仮定し、1つ目の総時間は3(d-a)である.a->c->a->b->d->c->dであれば、総消費時間は3(c-a)+3(d-b)-(c-b)=3 d+2 c-2 b-3 a>3 d-3 aである.ダブルポインタでシミュレートすればいいです.
#include
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
    re g=1;register char ch=getchar();res=0;
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
int n,m,k,t,p,q,X,Y,sum,lim,a[202000];
inline bool bbb(int x,int y){
    return x>y;
}
struct Barrier{
    int l,r,w;
    friend bool operator < (Barrier x,Barrier y){
        return x.l==y.l?x.rk)X=sum=0;
    else sum=X=b[p].l-1;
    while(p<=k){
        Y=b[p].r;
        q=p+1;
        while(q<=k&&(b[q].w<=lim||b[q].l<=Y)){
            if(b[q].w>lim)Y=max(Y,b[q].r);
            q++;
        }
        sum+=3*(Y-X);
        X=Y;
        if(q>k)break;
        sum+=(b[q].l-1-X);
        X=b[q].l-1;
        p=q;
    }
    sum+=(m-X);
    //cout<>1;
    if(ck(mid))x=mid;
    else y=mid-1;
    return divided(x,y);
}
int main(){
    read(n);read(m);read(k);read(t);m++;
    F(i,1,n){
        read(a[i]);
    }
    sort(a+1,a+1+n,bbb);
    F(i,1,k){
        read(b[i].l);read(b[i].r);read(b[i].w);
    }
    sort(b+1,b+1+k);
    b[k+1].l=0;
    if(m>t){
        cout<