oj.uz

Submission #25584

# Submission time Handle Problem Language Result Execution time Memory
25584 2017-06-23T06:16:08 Z suhgyuho_william 버스 (JOI14_bus) C++14
100 / 100
 303 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 0 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 3 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 0 ms 9056 KB Output is correct
11 Correct 0 ms 9056 KB Output is correct
12 Correct 0 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 43 ms 9056 KB Output is correct
3 Correct 43 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 23 ms 9056 KB Output is correct
8 Correct 0 ms 9056 KB Output is correct
9 Correct 26 ms 9056 KB Output is correct
10 Correct 29 ms 9056 KB Output is correct
11 Correct 26 ms 9188 KB Output is correct
12 Correct 43 ms 9192 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 9056 KB Output is correct
2 Correct 226 ms 9056 KB Output is correct
3 Correct 223 ms 9056 KB Output is correct
4 Correct 196 ms 9056 KB Output is correct
5 Correct 206 ms 9056 KB Output is correct
6 Correct 209 ms 9332 KB Output is correct
7 Correct 213 ms 9596 KB Output is correct
8 Correct 206 ms 10708 KB Output is correct
9 Correct 179 ms 9332 KB Output is correct
10 Correct 213 ms 9320 KB Output is correct
11 Correct 239 ms 9320 KB Output is correct
12 Correct 219 ms 9320 KB Output is correct
13 Correct 199 ms 9320 KB Output is correct
14 Correct 199 ms 9320 KB Output is correct
15 Correct 206 ms 9320 KB Output is correct
16 Correct 63 ms 12224 KB Output is correct
17 Correct 79 ms 12224 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 9056 KB Output is correct
2 Correct 289 ms 9056 KB Output is correct
3 Correct 243 ms 9056 KB Output is correct
4 Correct 276 ms 9056 KB Output is correct
5 Correct 266 ms 9056 KB Output is correct
6 Correct 276 ms 9332 KB Output is correct
7 Correct 303 ms 9596 KB Output is correct
8 Correct 296 ms 9332 KB Output is correct
9 Correct 226 ms 9332 KB Output is correct
10 Correct 256 ms 9320 KB Output is correct
11 Correct 246 ms 9320 KB Output is correct
12 Correct 263 ms 9320 KB Output is correct
13 Correct 279 ms 9320 KB Output is correct
14 Correct 269 ms 9320 KB Output is correct
15 Correct 286 ms 9320 KB Output is correct
16 Correct 106 ms 12224 KB Output is correct