oj.uz

Submission #199351

# Submission time Handle Problem Language Result Execution time Memory
199351 2020-01-31T15:50:16 Z arnold518 버스 (JOI14_bus) C++14
85 / 100
 274 ms 18012 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
		{
			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:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
bus.cpp:49: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 14 ms 12024 KB Output is correct
2 Correct 13 ms 12024 KB Output is correct
3 Correct 13 ms 12024 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 12 ms 12024 KB Output is correct
6 Correct 12 ms 12024 KB Output is correct
7 Correct 12 ms 12152 KB Output is correct
8 Correct 13 ms 12024 KB Output is correct
9 Correct 12 ms 12024 KB Output is correct
10 Correct 13 ms 12024 KB Output is correct
11 Correct 14 ms 12156 KB Output is correct
12 Correct 14 ms 12152 KB Output is correct
13 Correct 14 ms 12152 KB Output is correct
14 Correct 14 ms 12024 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 46 ms 12920 KB Output is correct
3 Correct 47 ms 12792 KB Output is correct
4 Correct 17 ms 12152 KB Output is correct
5 Correct 19 ms 12152 KB Output is correct
6 Correct 15 ms 12152 KB Output is correct
7 Correct 34 ms 12408 KB Output is correct
8 Correct 13 ms 12024 KB Output is correct
9 Correct 45 ms 12280 KB Output is correct
10 Correct 47 ms 12792 KB Output is correct
11 Correct 38 ms 12408 KB Output is correct
12 Correct 54 ms 13032 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 16764 KB Output is correct
2 Correct 239 ms 16748 KB Output is correct
3 Correct 230 ms 16760 KB Output is correct
4 Correct 235 ms 16760 KB Output is correct
5 Correct 235 ms 16760 KB Output is correct
6 Correct 222 ms 16888 KB Output is correct
7 Correct 224 ms 17144 KB Output is correct
8 Correct 226 ms 17788 KB Output is correct
9 Correct 234 ms 16888 KB Output is correct
10 Correct 222 ms 16888 KB Output is correct
11 Correct 215 ms 16888 KB Output is correct
12 Execution timed out 89 ms 15740 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 17400 KB Output is correct
2 Correct 255 ms 17144 KB Output is correct
3 Correct 266 ms 17528 KB Output is correct
4 Correct 274 ms 17656 KB Output is correct
5 Correct 250 ms 17148 KB Output is correct
6 Correct 271 ms 17404 KB Output is correct
7 Correct 268 ms 18012 KB Output is correct
8 Correct 254 ms 17632 KB Output is correct
9 Correct 256 ms 17656 KB Output is correct
10 Correct 264 ms 17656 KB Output is correct
11 Correct 253 ms 17784 KB Output is correct
12 Correct 239 ms 17656 KB Output is correct
13 Correct 243 ms 17784 KB Output is correct
14 Correct 247 ms 17656 KB Output is correct
15 Correct 241 ms 17656 KB Output is correct
16 Correct 128 ms 17016 KB Output is correct