oj.uz

Submission #14916

# Submission time Handle Problem Language Result Execution time Memory
14916 2015-07-06T04:50:58 Z comet 막대기 (KOI13_game) C++
100 / 100
 205 ms 27928 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16560 KB Output is correct
2 Correct 2 ms 16560 KB Output is correct
3 Correct 0 ms 16560 KB Output is correct
4 Correct 4 ms 16560 KB Output is correct
5 Correct 4 ms 16560 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17352 KB Output is correct
2 Correct 69 ms 17352 KB Output is correct
3 Correct 169 ms 17880 KB Output is correct
4 Correct 205 ms 17748 KB Output is correct
5 Correct 186 ms 17880 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16560 KB Output is correct
2 Correct 4 ms 16560 KB Output is correct
3 Correct 4 ms 16560 KB Output is correct
4 Correct 0 ms 16560 KB Output is correct
5 Correct 0 ms 16560 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16692 KB Output is correct
2 Correct 2 ms 16692 KB Output is correct
3 Correct 5 ms 16692 KB Output is correct
4 Correct 2 ms 16692 KB Output is correct
5 Correct 0 ms 16692 KB Output is correct
6 Correct 5 ms 16692 KB Output is correct
7 Correct 2 ms 16692 KB Output is correct

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16824 KB Output is correct
2 Correct 17 ms 16824 KB Output is correct
3 Correct 62 ms 19612 KB Output is correct
4 Correct 156 ms 19464 KB Output is correct
5 Correct 146 ms 19816 KB Output is correct
6 Correct 135 ms 20256 KB Output is correct
7 Correct 161 ms 20256 KB Output is correct
8 Correct 113 ms 27928 KB Output is correct
9 Correct 12 ms 16956 KB Output is correct
10 Correct 14 ms 16824 KB Output is correct
11 Correct 132 ms 24012 KB Output is correct
12 Correct 121 ms 23984 KB Output is correct