Submission #25565

#	Time	Username	Problem	Language	Result	Execution time	Memory
25565		youngyojun	버스 (JOI14_bus)	C++11	100 / 100	519 ms	31152 KiB

bus

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MOD (1000000007)
#define MAXN (100005)
#define MAXM (300005)
#define MAXQ (100005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int uptwo[MAXN] = {1, };
struct SEG {
	int *d; int MX;
	void init(const int SZ) { MX = uptwo[SZ]; d = new int[MX*2]; fill(d, d+(MX*2), INF); }
	void upd(int X, int R) { for(X += MX; X; X /= 2) upmin(d[X], R); }
	int get(int S, int E) {
		int r = INF; for(S += MX, E += MX; S <= E; S /= 2, E /= 2) {
			if(S&1) upmin(r, d[S++]); if(~E&1) upmin(r, d[E--]);
		} return r;
	}
};

SEG seg[MAXN];
vector<int> VT[MAXN];
int AnsT[MAXM];
int A[MAXM], B[MAXM], X[MAXM], Y[MAXM], P[MAXM];
int XI[MAXM], YI[MAXM];
int QT[MAXQ], QP[MAXQ];
int Ans[MAXQ];
int N, M, Q;

int main() {
	for(int i = 1; i < MAXN; i++) uptwo[i] = uptwo[i/2]*2;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++) scanf("%d%d%d%d", &A[i], &B[i], &X[i], &Y[i]);
	for(int i = 1; i <= M; i++) { VT[A[i]].pb(X[i]); VT[B[i]].pb(Y[i]); }
	for(int i = 1; i <= M; i++) P[i] = i;
	sort(P+1, P+M+1, [&](const int& a, const int& b) -> bool {
		return Y[a] > Y[b];
	});
	for(int i = 1; i <= N; i++) { sorv(VT[i]); univ(VT[i]); }
	for(int i = 1; i < N; i++) seg[i].init(sz(VT[i]));
	for(int i = 1; i <= M; i++) {
		XI[i] = (int)(lower_bound(allv(VT[A[i]]), X[i]) - VT[A[i]].begin()) + 1;
		YI[i] = (int)(lower_bound(allv(VT[B[i]]), Y[i]) - VT[B[i]].begin()) + 1;
	}
	for(int ei = 1; ei <= M; ei++) {
		const int idx = P[ei];
		if(A[idx] == N) continue;
		else if(B[idx] == N) {
			seg[A[idx]].upd(XI[idx], Y[idx]);
		} else {
			const int ret = seg[B[idx]].get(YI[idx], sz(VT[B[idx]]));
			if(INF <= ret) continue;
			seg[A[idx]].upd(XI[idx], ret);
		}
	}
	for(int i = 1; i <= sz(VT[1]); i++) AnsT[i] = seg[1].get(i, i);
	for(int i = sz(VT[1])-1; i; i--) upmin(AnsT[i], AnsT[i+1]);
	scanf("%d", &Q); for(int i = 1; i <= Q; i++) scanf("%d", &QT[i]);
	for(int i = 1; i <= Q; i++) QP[i] = i;
	sort(QP+1, QP+Q+1, [&](const int& a, const int& b) -> bool { return QT[a] < QT[b]; });
	for(int qi = 1, i = 1; qi <= Q; qi++) {
		const int idx = QP[qi];
		for(; i <= sz(VT[1]) && AnsT[i] <= QT[idx]; i++);
		Ans[idx] = (1 == i) ? -1 : VT[1][i-2];
	}
	for(int i = 1; i <= Q; i++) printf("%d\n", Ans[i]);
	return 0;
}

Compilation message (stderr)

bus.cpp: In function 'int main()':
bus.cpp:63:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
bus.cpp:64:75: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= M; i++) scanf("%d%d%d%d", &A[i], &B[i], &X[i], &Y[i]);
                                                                           ^
bus.cpp:89:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q); for(int i = 1; i <= Q; i++) scanf("%d", &QT[i]);
                 ^
bus.cpp:89:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q); for(int i = 1; i <= Q; i++) scanf("%d", &QT[i]);
                                                                  ^

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