Submission #10650

#	Time	Username	Problem	Language	Result	Execution time	Memory
10650		dohyun0324	버스 (JOI14_bus)	C++98	100 / 100	248 ms	10972 KiB

bus

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> ppair;
priority_queue< ppair,vector<ppair>,greater<ppair> >q;
int w,p,n,m,k,dap[300010],arr[300010],ch[300010],ans[300010];
struct data
{
    int a,b,x,y;
    bool operator<(const data&r)const
    {
        if(a==r.a) return x>r.x;
        return a<r.a;
    }
}d[300010];
void pro(int p)
{
    int i,j,s;
    while(q.size())
    {
        s=q.top().second; q.pop();
        for(i=arr[d[s].b];;i++)
        {
            if(d[i].a!=d[s].b || d[i].x<d[s].y) break;
            if(d[i].b==n) dap[p]=min(dap[p],d[i].y);
            q.push(make_pair(d[i].y,i));
        }
        arr[d[s].b]=i;
    }
}
int main()
{
    int i,*s,pos;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++) scanf("%d %d %d %d",&d[i].a,&d[i].b,&d[i].x,&d[i].y);
    sort(d+1,d+m+1);
    sort(d+1,d+m+1);
    dap[0]=-1;
    for(i=1;i<=m;i++)
    {
        if(d[i].a!=d[i-1].a) arr[d[i].a]=i;
    }
    for(i=1;i<=m;i++)
    {
        if(d[i].a!=1) break;
        q.push(make_pair(d[i].y,i));
        dap[++w]=2147483647;
        if(d[i].b==n) dap[w]=min(dap[w],d[i].y);
        pro(w);
        if(dap[w-1]!=-1 && dap[w]>dap[w-1]) dap[w]=dap[w-1];
        if(dap[w]==2147483647) dap[w]=-1;
        ans[w]=d[i].x;
    }
    reverse(dap+1,dap+w+1);
    reverse(ans+1,ans+w+1);
    while(dap[w]==-1) w--;
    scanf("%d",&k);
    dap[w+1]=2147483647; ans[0]=-1;
    for(i=1;i<=k;i++)
    {
        scanf("%d",&p);
        s=upper_bound(dap+1,dap+w+1,p);
        pos=s-dap;
        printf("%d\n",ans[pos-1]);
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50