oj.uz

Submission #25566

# Submission time Handle Problem Language Result Execution time Memory
25566 2017-06-23T05:33:50 Z zigui 버스 (JOI14_bus) C++14
100 / 100
 443 ms 125368 KB 
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

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

const int MX = 100005;

struct bus{
	bus(){}
	bus(int src, int dst, int p, int q):src(src), dst(dst), p(p), q(q){}
	int src, dst, p, q;
	bool operator<(const bus &l)const{
		return p < l.p;
	}
} D[MX*3];

deque<pii> T[MX];
int N, M;
int a, b, c, d;

pii get_time(bus c){
	int d = c.dst;
	if( d == N ) return pii(c.p, c.q);
	else{
//		for(pii c : T[d]) printf("%d %d\n", c.first, c.second);
//		printf("find : %d %d\n\n", c.q, (int)1e9);
		auto it = lower_bound(T[d].begin(), T[d].end(), pii(c.q, -1e9));
		if( it == T[d].end() ) return pii(c.p, 1e9);
		else return pii(c.p, it->second);
	}
}

void insert(deque<pii> &X, pii c){
	if( X.empty() || X.front().second > c.second ) X.push_front(c);
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		D[i] = bus(a, b, c, d);
	}
	sort(D+1, D+M+1);
	for(int i = M; i >= 1; i--){
		pii c = get_time(D[i]);
		insert(T[D[i].src], c);
	}

	vector<pii> X;
	for(pii c : T[1]) X.emplace_back(c.second, c.first);
	int Q;
	scanf("%d", &Q);
	for(int i = 1; i <= Q; i++){
		scanf("%d", &a);
		auto it = upper_bound(X.begin(), X.end(), pii(a, 1e9));
		if( it == X.begin() ) printf("-1\n");
		else printf("%d\n", (--it)->second);
	}
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:46:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
bus.cpp:48:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
                                    ^
bus.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
bus.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 73888 KB Output is correct
2 Correct 26 ms 73888 KB Output is correct
3 Correct 39 ms 74020 KB Output is correct
4 Correct 23 ms 74020 KB Output is correct
5 Correct 26 ms 73888 KB Output is correct
6 Correct 33 ms 73888 KB Output is correct
7 Correct 23 ms 73888 KB Output is correct
8 Correct 33 ms 74020 KB Output is correct
9 Correct 23 ms 74152 KB Output is correct
10 Correct 36 ms 74152 KB Output is correct
11 Correct 33 ms 74416 KB Output is correct
12 Correct 23 ms 73888 KB Output is correct
13 Correct 33 ms 74812 KB Output is correct
14 Correct 23 ms 73888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 73888 KB Output is correct
2 Correct 93 ms 73888 KB Output is correct
3 Correct 73 ms 74020 KB Output is correct
4 Correct 29 ms 74020 KB Output is correct
5 Correct 46 ms 73888 KB Output is correct
6 Correct 26 ms 73888 KB Output is correct
7 Correct 73 ms 73888 KB Output is correct
8 Correct 29 ms 73888 KB Output is correct
9 Correct 53 ms 74152 KB Output is correct
10 Correct 63 ms 74416 KB Output is correct
11 Correct 79 ms 74812 KB Output is correct
12 Correct 79 ms 73888 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 122860 KB Output is correct
2 Correct 403 ms 122860 KB Output is correct
3 Correct 339 ms 122728 KB Output is correct
4 Correct 293 ms 122860 KB Output is correct
5 Correct 363 ms 122728 KB Output is correct
6 Correct 333 ms 122332 KB Output is correct
7 Correct 249 ms 78904 KB Output is correct
8 Correct 353 ms 117976 KB Output is correct
9 Correct 423 ms 122332 KB Output is correct
10 Correct 303 ms 74152 KB Output is correct
11 Correct 266 ms 74152 KB Output is correct
12 Correct 253 ms 74152 KB Output is correct
13 Correct 283 ms 74152 KB Output is correct
14 Correct 303 ms 74152 KB Output is correct
15 Correct 256 ms 74152 KB Output is correct
16 Correct 203 ms 125368 KB Output is correct
17 Correct 159 ms 125368 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 122860 KB Output is correct
2 Correct 386 ms 122860 KB Output is correct
3 Correct 383 ms 122728 KB Output is correct
4 Correct 373 ms 122860 KB Output is correct
5 Correct 416 ms 122728 KB Output is correct
6 Correct 436 ms 122332 KB Output is correct
7 Correct 289 ms 78904 KB Output is correct
8 Correct 389 ms 122332 KB Output is correct
9 Correct 443 ms 122332 KB Output is correct
10 Correct 309 ms 74152 KB Output is correct
11 Correct 329 ms 74152 KB Output is correct
12 Correct 296 ms 74152 KB Output is correct
13 Correct 336 ms 74152 KB Output is correct
14 Correct 329 ms 74152 KB Output is correct
15 Correct 253 ms 74152 KB Output is correct
16 Correct 196 ms 125368 KB Output is correct