oj.uz

Submission #199359

# Submission time Handle Problem Language Result Execution time Memory
199359 2020-01-31T16:03:40 Z arnold518 버스 (JOI14_bus) C++14
100 / 100
 278 ms 24440 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12024 KB Output is correct
2 Correct 14 ms 12024 KB Output is correct
3 Correct 13 ms 12024 KB Output is correct
4 Correct 13 ms 12024 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12024 KB Output is correct
7 Correct 13 ms 12024 KB Output is correct
8 Correct 13 ms 12024 KB Output is correct
9 Correct 15 ms 12024 KB Output is correct
10 Correct 13 ms 12028 KB Output is correct
11 Correct 14 ms 12152 KB Output is correct
12 Correct 14 ms 12152 KB Output is correct
13 Correct 16 ms 12280 KB Output is correct
14 Correct 15 ms 12284 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Correct 47 ms 12920 KB Output is correct
3 Correct 50 ms 12792 KB Output is correct
4 Correct 17 ms 12152 KB Output is correct
5 Correct 17 ms 12152 KB Output is correct
6 Correct 17 ms 12152 KB Output is correct
7 Correct 37 ms 12408 KB Output is correct
8 Correct 14 ms 12024 KB Output is correct
9 Correct 36 ms 12280 KB Output is correct
10 Correct 48 ms 12796 KB Output is correct
11 Correct 36 ms 12408 KB Output is correct
12 Correct 54 ms 12920 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 16888 KB Output is correct
2 Correct 228 ms 16888 KB Output is correct
3 Correct 237 ms 16760 KB Output is correct
4 Correct 232 ms 16740 KB Output is correct
5 Correct 242 ms 16760 KB Output is correct
6 Correct 222 ms 16888 KB Output is correct
7 Correct 222 ms 17272 KB Output is correct
8 Correct 230 ms 17784 KB Output is correct
9 Correct 231 ms 16924 KB Output is correct
10 Correct 217 ms 16888 KB Output is correct
11 Correct 217 ms 16888 KB Output is correct
12 Correct 220 ms 20704 KB Output is correct
13 Correct 218 ms 24440 KB Output is correct
14 Correct 224 ms 24440 KB Output is correct
15 Correct 224 ms 24380 KB Output is correct
16 Correct 83 ms 19320 KB Output is correct
17 Correct 96 ms 19308 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 17400 KB Output is correct
2 Correct 261 ms 17136 KB Output is correct
3 Correct 267 ms 17528 KB Output is correct
4 Correct 259 ms 17656 KB Output is correct
5 Correct 261 ms 17144 KB Output is correct
6 Correct 264 ms 17528 KB Output is correct
7 Correct 259 ms 18168 KB Output is correct
8 Correct 255 ms 17676 KB Output is correct
9 Correct 251 ms 17784 KB Output is correct
10 Correct 278 ms 17792 KB Output is correct
11 Correct 255 ms 17760 KB Output is correct
12 Correct 248 ms 17784 KB Output is correct
13 Correct 240 ms 17656 KB Output is correct
14 Correct 253 ms 17656 KB Output is correct
15 Correct 250 ms 17656 KB Output is correct
16 Correct 108 ms 17016 KB Output is correct