Submission #14916

#	Time	Username	Problem	Language	Result	Execution time	Memory
14916		comet	막대기 (KOI13_game)	C++98	100 / 100	205 ms	27928 KiB

game

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll n,L;
struct line{
    ll u,v;
    line(int uu=0,int vv=0){
        u=uu,v=vv;
    }
}UP[100010],DOWN[100010];
vector<int> up[200010],down[200010];
bool cmp(line x,line y){
    return x.u!=y.u?x.u<y.u:x.v<y.v;
}
bool cmp2(line x,line y){
    return x.v!=y.v?x.v<y.v:x.u<y.u;
}
int lu[200010],sz;
ll d[100010][2];
ll f(int x,int k){
 
    ll &ret=d[x][k];
    if(ret)return ret;
    int lo=0,hi=0,mid,z;
    if(k==0){
        //cout<<"x=("<<UP[x].u<<", "<<UP[x].v<<") k= "<<k<<endl;
        hi=up[UP[x].u].size();
        while(lo+1<hi){
            mid=(lo+hi)/2;
            if(DOWN[up[UP[x].u][mid]].v>UP[x].v)hi=mid;
            else lo=mid;
        }
        for(int i=hi;i<up[UP[x].u].size();i++){
            z=up[UP[x].u][i];
            ret=max(ret,f(z,1));
            break;
        }
        ret+=abs(lu[UP[x].v]-lu[UP[x].u])+L;
 
        lo=0;
        hi=down[UP[x].v].size();
        while(lo+1<hi){
            mid=(lo+hi)/2;
            if(UP[down[UP[x].v][mid]].u>UP[x].u)hi=mid;
            else lo=mid;
        }
        //for(int i=0;i<down[UP[x].v].size();i++)cout<<UP[down[UP[x].v][i]].u<<","<<UP[down[UP[x].v][i]].v<<" ";
        //cout<<endl;
        if(hi<down[UP[x].v].size())ret=max(ret,f(down[UP[x].v][hi],k));
    }
    else{
        //cout<<"x=("<<DOWN[x].u<<", "<<DOWN[x].v<<") k= "<<k<<endl;
        hi=down[DOWN[x].v].size();
        while(lo+1<hi){
            mid=(lo+hi)/2;
            if(UP[down[DOWN[x].v][mid]].u>DOWN[x].u)hi=mid;
            else lo=mid;
        }
        for(int i=hi;i<down[DOWN[x].v].size();i++){
            z=down[DOWN[x].v][i];
            ret=max(ret,f(z,0));
        }
        ret+=abs(lu[DOWN[x].v]-lu[DOWN[x].u])+L;
 
        lo=0;
        hi=up[DOWN[x].u].size();
        while(lo+1<hi){
            mid=(lo+hi)/2;
            if(DOWN[up[DOWN[x].u][mid]].v>DOWN[x].v)hi=mid;
            else lo=mid;
        }
        if(hi<up[DOWN[x].u].size())ret=max(ret,f(up[DOWN[x].u][hi],k));
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>L;
    ll x,y;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        lu[sz++]=x;
        lu[sz++]=y;
        UP[i]=line(x,y);
        DOWN[i]=line(x,y);
    }
    sort(lu,lu+sz);
    sz=unique(lu,lu+sz)-lu;
    for(int i=0;i<n;i++){
        UP[i].u=lower_bound(lu,lu+sz,UP[i].u)-lu;
        UP[i].v=lower_bound(lu,lu+sz,UP[i].v)-lu;
        DOWN[i]=UP[i];
    }
    sort(UP,UP+n,cmp);
    sort(DOWN,DOWN+n,cmp2);
    for(int i=0;i<n;i++){
        down[UP[i].v].push_back(i);
        up[DOWN[i].u].push_back(i);
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        if(UP[i].u<=UP[down[UP[i].v][0]].u){
            ans=max(ans,f(i,0));
        }
        if(DOWN[i].v<=DOWN[up[DOWN[i].u][0]].v){
            ans=max(ans,f(i,1));
        }
    }
    cout<<ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38