Submission #199359

#	Time	Username	Problem	Language	Result	Execution time	Memory
199359		arnold518	버스 (JOI14_bus)	C++14	100 / 100	278 ms	24440 KiB

bus

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const int MAXM = 5e5;

struct Data
{
	int A, B, X, Y;
};

int N, M, Q;
Data E[MAXM+10];
vector<pii> A[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++) scanf("%d%d%d%d", &E[i].A, &E[i].B, &E[i].X, &E[i].Y);
	sort(E+1, E+M+1, [&](const Data &p, const Data &q) { return p.X>q.X; });

	for(i=1; i<=M; i++)
	{
		if(E[i].A==N) continue;
		int v;
		if(E[i].B==N) v=E[i].Y;
		else
		{
			assert(is_sorted(A[E[i].B].begin(), A[E[i].B].end(), greater<pii>()));
			auto it=upper_bound(A[E[i].B].begin(), A[E[i].B].end(), pii(E[i].Y, -1), greater<pii>());
			if(it==A[E[i].B].begin()) v=-1;
			else v=(it-1)->second;
		}
		if(v!=-1 && (A[E[i].A].empty() || A[E[i].A].back().second>v)) A[E[i].A].push_back({E[i].X, v});
	}

	map<int, int> M;
	for(auto it : A[1]) M[it.second]=it.first;
	
	scanf("%d", &Q);
	while(Q--)
	{
		int x;
		scanf("%d", &x);
		auto it=M.upper_bound(x);
		if(it==M.begin()) printf("-1\n");
		else printf("%d\n", (--it)->second);
	}
}

Compilation message (stderr)

bus.cpp: In function 'int main()':
bus.cpp:22:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
bus.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
bus.cpp:25:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d%d%d", &E[i].A, &E[i].B, &E[i].X, &E[i].Y);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bus.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
bus.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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