oj.uz

Submission #25575

# Submission time Handle Problem Language Result Execution time Memory
25575 2017-06-23T05:55:27 Z 서규호(#1074) 버스 (JOI14_bus) C++14
100 / 100
 299 ms 12224 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,Q,ans;
struct data{
	int x,y,tx,ty;
}edge[300002];
vector<pair<int,pp>> d[100002];
priority_queue<pp> q;
vector<int> print;

int main(){
	scanf("%d %d",&N,&M);
	for(int i=1; i<=M; i++){
		scanf("%d %d %d %d",&edge[i].x,&edge[i].y,&edge[i].tx,&edge[i].ty);
		if(edge[i].x == 1) print.pb(edge[i].tx);
	}
	sort(edge+1,edge+M+1,[&](data &x,data &y){
		return x.ty < y.ty;
	});
	sort(print.begin(),print.end());
	for(int i=0; i<print.size(); i++) d[1].pb({print[i],{i,i}});
	for(int i=1; i<=M; i++){
		int x,y,tx,ty;
		x = edge[i].x; y = edge[i].y; tx = edge[i].tx; ty = edge[i].ty;
		if(d[x].size() == 0 || d[x][0].first > tx) continue;
		int l,r,t;
		l = 0; r = d[x].size()-1;
		while(l <= r){
			int mid = (l+r)/2;
			if(d[x][mid].first <= tx){
				t = mid;
				l = mid+1;
			}else r = mid-1;
		}
		int e = d[x][t].second.second;
		if(d[y].size() == 0 || d[y].back().second.second < e){
            int tt;
            if(d[y].size() == 0) tt = 0;
            else tt = d[y].back().second.second+1;
			d[y].pb({ty,{tt,e}});
		}
	}

	scanf("%d",&Q);
	for(int i=1; i<=Q; i++){
		int query;
		scanf("%d",&query);
		if(d[N].size() == 0 || query < d[N][0].first){
			ans = -1;
		}else{
			int l,r,t;
			l = 0; r = d[N].size()-1;
			while(l <= r){
				int mid = (l+r)/2;
				if(d[N][mid].first <= query){
					t = mid;
					l = mid+1;
				}else r = mid-1;
			}
			t = d[N][t].second.second;
			ans = print[t];
		}
		printf("%d\n",ans);
	}

	return 0;
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<print.size(); i++) d[1].pb({print[i],{i,i}});
                ^
bus.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
bus.cpp:27:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&edge[i].x,&edge[i].y,&edge[i].tx,&edge[i].ty);
                                                                     ^
bus.cpp:57:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
bus.cpp:60:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&query);
                     ^
bus.cpp:73:14: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
    t = d[N][t].second.second;
              ^
bus.cpp:48:17: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int e = d[x][t].second.second;
                 ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9056 KB Output is correct
2 Correct 0 ms 9056 KB Output is correct
3 Correct 0 ms 9056 KB Output is correct
4 Correct 0 ms 9056 KB Output is correct
5 Correct 0 ms 9056 KB Output is correct
6 Correct 0 ms 9056 KB Output is correct
7 Correct 0 ms 9056 KB Output is correct
8 Correct 0 ms 9056 KB Output is correct
9 Correct 0 ms 9056 KB Output is correct
10 Correct 3 ms 9056 KB Output is correct
11 Correct 3 ms 9056 KB Output is correct
12 Correct 3 ms 9056 KB Output is correct
13 Correct 0 ms 9188 KB Output is correct
14 Correct 0 ms 9192 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9056 KB Output is correct
2 Correct 23 ms 9056 KB Output is correct
3 Correct 36 ms 9056 KB Output is correct
4 Correct 3 ms 9056 KB Output is correct
5 Correct 3 ms 9056 KB Output is correct
6 Correct 3 ms 9056 KB Output is correct
7 Correct 36 ms 9056 KB Output is correct
8 Correct 0 ms 9056 KB Output is correct
9 Correct 33 ms 9056 KB Output is correct
10 Correct 33 ms 9056 KB Output is correct
11 Correct 23 ms 9188 KB Output is correct
12 Correct 36 ms 9192 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 9056 KB Output is correct
2 Correct 199 ms 9056 KB Output is correct
3 Correct 279 ms 9056 KB Output is correct
4 Correct 206 ms 9056 KB Output is correct
5 Correct 243 ms 9056 KB Output is correct
6 Correct 189 ms 9332 KB Output is correct
7 Correct 213 ms 9596 KB Output is correct
8 Correct 253 ms 10708 KB Output is correct
9 Correct 243 ms 9332 KB Output is correct
10 Correct 193 ms 9320 KB Output is correct
11 Correct 203 ms 9320 KB Output is correct
12 Correct 229 ms 9320 KB Output is correct
13 Correct 243 ms 9320 KB Output is correct
14 Correct 236 ms 9320 KB Output is correct
15 Correct 196 ms 9320 KB Output is correct
16 Correct 73 ms 12224 KB Output is correct
17 Correct 69 ms 12224 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 9056 KB Output is correct
2 Correct 263 ms 9056 KB Output is correct
3 Correct 263 ms 9056 KB Output is correct
4 Correct 233 ms 9056 KB Output is correct
5 Correct 233 ms 9056 KB Output is correct
6 Correct 246 ms 9332 KB Output is correct
7 Correct 253 ms 9596 KB Output is correct
8 Correct 299 ms 9332 KB Output is correct
9 Correct 283 ms 9332 KB Output is correct
10 Correct 243 ms 9320 KB Output is correct
11 Correct 203 ms 9320 KB Output is correct
12 Correct 266 ms 9320 KB Output is correct
13 Correct 223 ms 9320 KB Output is correct
14 Correct 263 ms 9320 KB Output is correct
15 Correct 276 ms 9320 KB Output is correct
16 Correct 89 ms 12224 KB Output is correct