oj.uz

Submission #10650

# Submission time Handle Problem Language Result Execution time Memory
10650 2014-11-02T07:15:19 Z dohyun0324 버스 (JOI14_bus) C++
100 / 100
 248 ms 10972 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10584 KB Output is correct
2 Correct 0 ms 10584 KB Output is correct
3 Correct 0 ms 10584 KB Output is correct
4 Correct 0 ms 10584 KB Output is correct
5 Correct 0 ms 10584 KB Output is correct
6 Correct 0 ms 10584 KB Output is correct
7 Correct 0 ms 10584 KB Output is correct
8 Correct 0 ms 10584 KB Output is correct
9 Correct 0 ms 10584 KB Output is correct
10 Correct 0 ms 10584 KB Output is correct
11 Correct 0 ms 10584 KB Output is correct
12 Correct 0 ms 10584 KB Output is correct
13 Correct 0 ms 10584 KB Output is correct
14 Correct 0 ms 10584 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10584 KB Output is correct
2 Correct 32 ms 10584 KB Output is correct
3 Correct 36 ms 10584 KB Output is correct
4 Correct 4 ms 10584 KB Output is correct
5 Correct 4 ms 10584 KB Output is correct
6 Correct 0 ms 10584 KB Output is correct
7 Correct 24 ms 10584 KB Output is correct
8 Correct 0 ms 10584 KB Output is correct
9 Correct 28 ms 10584 KB Output is correct
10 Correct 32 ms 10584 KB Output is correct
11 Correct 28 ms 10584 KB Output is correct
12 Correct 36 ms 10584 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 10584 KB Output is correct
2 Correct 196 ms 10584 KB Output is correct
3 Correct 204 ms 10584 KB Output is correct
4 Correct 204 ms 10584 KB Output is correct
5 Correct 188 ms 10584 KB Output is correct
6 Correct 188 ms 10584 KB Output is correct
7 Correct 188 ms 10584 KB Output is correct
8 Correct 200 ms 10584 KB Output is correct
9 Correct 208 ms 10584 KB Output is correct
10 Correct 212 ms 10972 KB Output is correct
11 Correct 232 ms 10716 KB Output is correct
12 Correct 220 ms 10716 KB Output is correct
13 Correct 216 ms 10716 KB Output is correct
14 Correct 212 ms 10716 KB Output is correct
15 Correct 208 ms 10716 KB Output is correct
16 Correct 56 ms 10584 KB Output is correct
17 Correct 60 ms 10584 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 10584 KB Output is correct
2 Correct 232 ms 10584 KB Output is correct
3 Correct 220 ms 10584 KB Output is correct
4 Correct 228 ms 10584 KB Output is correct
5 Correct 228 ms 10584 KB Output is correct
6 Correct 240 ms 10584 KB Output is correct
7 Correct 228 ms 10584 KB Output is correct
8 Correct 212 ms 10584 KB Output is correct
9 Correct 240 ms 10584 KB Output is correct
10 Correct 244 ms 10972 KB Output is correct
11 Correct 232 ms 10716 KB Output is correct
12 Correct 248 ms 10972 KB Output is correct
13 Correct 240 ms 10716 KB Output is correct
14 Correct 240 ms 10716 KB Output is correct
15 Correct 236 ms 10716 KB Output is correct
16 Correct 80 ms 10584 KB Output is correct