oj.uz

Submission #5777

# Submission time Handle Problem Language Result Execution time Memory
5777 2014-05-17T08:44:56 Z tncks0121 버스 (JOI14_bus) C++
20 / 100
 184 ms 9028 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.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 departed[N_], opt[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(departed, -1, sizeof departed);
 
    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;
            departed[y] = max(departed[y], opt[s.p]);
        }
 
        int &dt = opt[i];
        dt = (D[i].a == 1) ? D[i].x : departed[D[i].a];
 
        if(dt < 0) continue;
 
        PQ.push ( state(i,  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 && it != ans.end() ? -1 : it->second);
        }
    }
 
 
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9028 KB Output is correct
2 Correct 40 ms 9028 KB Output is correct
3 Correct 32 ms 9028 KB Output is correct
4 Correct 4 ms 9028 KB Output is correct
5 Correct 0 ms 9028 KB Output is correct
6 Correct 4 ms 9028 KB Output is correct
7 Correct 24 ms 9028 KB Output is correct
8 Incorrect 0 ms 9028 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 184 ms 9024 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 180 ms 9024 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -