oj.uz

Submission #163191

# Submission time Handle Problem Language Result Execution time Memory
163191 2019-11-11T17:59:25 Z TadijaSebez 버스 (JOI14_bus) C++11
100 / 100
 757 ms 40360 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=100050;
const int M=3*N;
map<int,int> dp[N];
int u[M],v[M],l[M],r[M],id[M];
int Get(int u, int tme){ return (--dp[u].upper_bound(tme))->second;}
int main()
{
	int n,m,q;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) dp[i][-1]=-1;
	for(int i=1;i<=m;i++)
	{
		scanf("%i %i %i %i",&u[i],&v[i],&l[i],&r[i]);
		if(u[i]==1) dp[1][l[i]]=l[i];
		if(v[i]==1) dp[1][r[i]]=r[i];
		id[i]=i;
	}
	sort(id+1,id+1+m,[&](int i, int j){ return r[i]<r[j];});
	for(int j=1;j<=m;j++)
	{
		int i=id[j];
		int mx=max(Get(v[i],r[i]),Get(u[i],l[i]));
		dp[v[i]][r[i]]=mx;
	}
	scanf("%i",&q);
	while(q--)
	{
		int x;
		scanf("%i",&x);
		printf("%i\n",Get(n,x));
	}
	return 0;
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bus.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i %i",&u[i],&v[i],&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bus.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
bus.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&x);
   ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5084 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5116 KB Output is correct
5 Correct 7 ms 5116 KB Output is correct
6 Correct 7 ms 5160 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5116 KB Output is correct
9 Correct 7 ms 5144 KB Output is correct
10 Correct 7 ms 5108 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 9 ms 5368 KB Output is correct
13 Correct 8 ms 5368 KB Output is correct
14 Correct 9 ms 5496 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 43 ms 6776 KB Output is correct
3 Correct 43 ms 6776 KB Output is correct
4 Correct 10 ms 5240 KB Output is correct
5 Correct 11 ms 5240 KB Output is correct
6 Correct 9 ms 5112 KB Output is correct
7 Correct 32 ms 5752 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 34 ms 5880 KB Output is correct
10 Correct 47 ms 6904 KB Output is correct
11 Correct 34 ms 6008 KB Output is correct
12 Correct 51 ms 7292 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 38412 KB Output is correct
2 Correct 457 ms 38436 KB Output is correct
3 Correct 463 ms 38392 KB Output is correct
4 Correct 453 ms 38520 KB Output is correct
5 Correct 433 ms 38392 KB Output is correct
6 Correct 520 ms 38552 KB Output is correct
7 Correct 446 ms 33656 KB Output is correct
8 Correct 486 ms 39780 KB Output is correct
9 Correct 443 ms 38652 KB Output is correct
10 Correct 478 ms 32496 KB Output is correct
11 Correct 543 ms 32636 KB Output is correct
12 Correct 481 ms 32632 KB Output is correct
13 Correct 500 ms 32584 KB Output is correct
14 Correct 494 ms 32504 KB Output is correct
15 Correct 499 ms 32504 KB Output is correct
16 Correct 110 ms 18856 KB Output is correct
17 Correct 112 ms 18908 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 39992 KB Output is correct
2 Correct 501 ms 39672 KB Output is correct
3 Correct 478 ms 40028 KB Output is correct
4 Correct 508 ms 40360 KB Output is correct
5 Correct 475 ms 39672 KB Output is correct
6 Correct 522 ms 40068 KB Output is correct
7 Correct 550 ms 35488 KB Output is correct
8 Correct 494 ms 40056 KB Output is correct
9 Correct 497 ms 40128 KB Output is correct
10 Correct 539 ms 34252 KB Output is correct
11 Correct 540 ms 34116 KB Output is correct
12 Correct 540 ms 34184 KB Output is correct
13 Correct 549 ms 34216 KB Output is correct
14 Correct 533 ms 34180 KB Output is correct
15 Correct 757 ms 34136 KB Output is correct
16 Correct 149 ms 19788 KB Output is correct