Submission #5777

#	Time	Username	Problem	Language	Result	Execution time	Memory
5777		tncks0121	버스 (JOI14_bus)	C++98	20 / 100	184 ms	9028 KiB

bus

#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 / 20
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50