oj.uz

Submission #199360

# Submission time Handle Problem Language Result Execution time Memory
199360 2020-01-31T16:04:19 Z arnold518 버스 (JOI14_bus) C++14
100 / 100
 288 ms 18168 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 12 ms 12024 KB Output is correct
2 Correct 13 ms 12024 KB Output is correct
3 Correct 14 ms 12024 KB Output is correct
4 Correct 13 ms 12024 KB Output is correct
5 Correct 13 ms 12024 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Correct 13 ms 12152 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 12024 KB Output is correct
11 Correct 14 ms 12152 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 12152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12024 KB Output is correct
2 Correct 47 ms 12920 KB Output is correct
3 Correct 46 ms 12792 KB Output is correct
4 Correct 16 ms 12152 KB Output is correct
5 Correct 16 ms 12152 KB Output is correct
6 Correct 15 ms 12152 KB Output is correct
7 Correct 32 ms 12408 KB Output is correct
8 Correct 13 ms 12152 KB Output is correct
9 Correct 35 ms 12408 KB Output is correct
10 Correct 47 ms 12792 KB Output is correct
11 Correct 38 ms 12408 KB Output is correct
12 Correct 51 ms 12920 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 16760 KB Output is correct
2 Correct 228 ms 16712 KB Output is correct
3 Correct 224 ms 16760 KB Output is correct
4 Correct 221 ms 16888 KB Output is correct
5 Correct 216 ms 16888 KB Output is correct
6 Correct 229 ms 16888 KB Output is correct
7 Correct 222 ms 17272 KB Output is correct
8 Correct 226 ms 17784 KB Output is correct
9 Correct 244 ms 16904 KB Output is correct
10 Correct 202 ms 16888 KB Output is correct
11 Correct 206 ms 17016 KB Output is correct
12 Correct 224 ms 16888 KB Output is correct
13 Correct 206 ms 16888 KB Output is correct
14 Correct 211 ms 16888 KB Output is correct
15 Correct 205 ms 17016 KB Output is correct
16 Correct 87 ms 16760 KB Output is correct
17 Correct 84 ms 16760 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 17364 KB Output is correct
2 Correct 264 ms 17144 KB Output is correct
3 Correct 256 ms 17532 KB Output is correct
4 Correct 252 ms 17528 KB Output is correct
5 Correct 245 ms 17144 KB Output is correct
6 Correct 246 ms 17400 KB Output is correct
7 Correct 288 ms 18168 KB Output is correct
8 Correct 259 ms 17528 KB Output is correct
9 Correct 257 ms 17656 KB Output is correct
10 Correct 242 ms 17784 KB Output is correct
11 Correct 235 ms 17656 KB Output is correct
12 Correct 240 ms 17788 KB Output is correct
13 Correct 242 ms 17656 KB Output is correct
14 Correct 240 ms 17664 KB Output is correct
15 Correct 240 ms 17700 KB Output is correct
16 Correct 106 ms 17016 KB Output is correct