oj.uz

Submission #5769

# Submission time Handle Problem Language Result Execution time Memory
5769 2014-05-17T03:12:12 Z tncks0121 버스 (JOI14_bus) C++
0 / 100
 184 ms 9496 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <bits/stdc++.h>
#include <memory.h>

typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef unsigned int uint;

using namespace std;

typedef pair<int, int> pii;

const int N_ = 100005;
const int M_ = 300005;

int N, M, Q;

struct bus {
    int a, b, x, y;
    bus (int a = 0, int b = 0, int x = 0, int y = 0): a(a), b(b), x(x), y(y) { }
    bool operator < (const bus &b) const { return x < b.x; }
} D[M_];

int T[M_+M_];

struct state {
    int p, t;
    state (int p = 0, int t = 0): p(p), t(t) { }
    bool operator < (const state &s) const { return t < s.t; }
    bool operator > (const state &s) const { return t > s.t; }
};

priority_queue <state, vector<state>, greater<state> > PQ;
int arrived[N_], departed[N_];

map<int, int> V;
vector<pii> ans;

int main() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int a, b, x, y;
        scanf("%d%d%d%d", &a, &b, &x, &y);
        D[i] = bus(a, b, x, y);
    }

    sort(D + 1, D + M + 1);
    memset(arrived, -1, sizeof arrived);

    for(int i = 1; i <= M; i++) {
        while(!PQ.empty() && PQ.top().t <= D[i].x) {
            state s = PQ.top(); PQ.pop();
            int y = D[s.p].b;
            arrived[y] = max(arrived[y], departed[s.p]);
        }

        int &dt = departed[i];
        dt = (D[i].a == 1) ? D[i].x : arrived[D[i].a];

        if(dt < 0) continue;

        PQ.push ( state(D[i].b, D[i].y) );
        if(D[i].b == N) {
            if(V.find(D[i].y) != V.end()) V[D[i].y] = min(V[D[i].y], dt);
            else V[D[i].y] = dt;
        }
    }

    int v = -100;
    for(map<int,int>::iterator it = V.begin(); it != V.end(); it++) {
        int at = it->first, dt = it->second;
        if(dt > v) ans.push_back( pii(at, dt) ), v = dt;
    }

    scanf("%d", &Q);
    while(Q--) {
        int t; scanf("%d", &t);
        if(ans.empty()) puts("-1");
        else {
            vector<pii>::iterator it = upper_bound(ans.begin(), ans.end(), pii(t, (int)1e9)); --it;
            printf("%d\n", t < ans[0].first ? -1 : it->second);
        }
    }


    return 0;
}

Subtask #1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9496 KB Output is correct
2 Correct 4 ms 9496 KB Output is correct
3 Correct 0 ms 9496 KB Output is correct
4 Correct 0 ms 9496 KB Output is correct
5 Incorrect 0 ms 9496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9496 KB Output is correct
2 Correct 32 ms 9496 KB Output is correct
3 Correct 36 ms 9496 KB Output is correct
4 Correct 0 ms 9496 KB Output is correct
5 Incorrect 4 ms 9496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 9492 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 184 ms 9492 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -