oj.uz

답안 #25563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25563 2017-06-23T05:21:12 Z 김동현(#1072) 버스 (JOI14_bus) C++14
0 / 100
 223 ms 15776 KB 
#include <bits/stdc++.h>
using namespace std;

struct E{
	int s, e, st, et;
	bool operator<(const E &oth) const {
		return et > oth.et;
	}
};

struct Dat{
	int st, ct;
	bool operator<(const Dat &oth) const {
		return ct == oth.ct ? st > oth.st : ct < oth.ct;
	}
};

struct Qry{
	int t, i;
	bool operator<(const Qry &oth) const {
		return t > oth.t;
	}
};

struct Ans{
	int t, v;
	bool operator<(const Ans &oth) const {
		return t == oth.t ? v > oth.v : t < oth.t;
	}
};

const int inf = 1e9;
struct Nod{
	int v;
	Nod *l, *r;
	Nod() : v(inf), l(nullptr), r(nullptr) {}
};

const int sz = 86400001;
struct Seg{
	Nod *rt;
	void ini(){ rt = new Nod(); }
	void upd(int x, int v, Nod *c, int p, int q){
		if(p == q){ c->v = v; return; }
		int m = (p + q) / 2;
		if(x <= m){
			if(c->l == nullptr) c->l = new Nod();
			upd(x, v, c->l, p, m);
			c->v = min(c->v, c->l->v);
		}
		else{
			if(c->r == nullptr) c->r = new Nod();
			upd(x, v, c->r, m + 1, q);
			c->v = min(c->v, c->r->v);
		}
	}
	void upd(int x, int v){ upd(x + 1, v, rt, 1, sz); }
	int get(int s, int e, Nod *c, int p, int q){
		if(e < p || q < s) return inf;
		if(s <= p && q <= e) return c->v;
		int m = (p + q) / 2, ret = inf;
		if(c->l != nullptr) ret = min(ret, get(s, e, c->l, p, m));
		if(c->r != nullptr) ret = min(ret, get(s, e, c->r, m + 1, q));
		return ret;
	}
	int get(int s, int e){ return get(s + 1, e + 1, rt, 1, sz); }
} S[100010];

int n, m, q, j, ans[100010];
vector<Ans> av;
vector<E> el;
vector<Qry> ql;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0, s, e, st, et; i < m; i++){
		scanf("%d%d%d%d", &s, &e, &st, &et);
		el.push_back({s, e, st, et});
	}
	sort(el.begin(), el.end());
	scanf("%d", &q);
	for(int i = 0, t; i < q; i++){
		scanf("%d", &t);
		ql.push_back({t, i});
	}
	ql.push_back({-1, q});
	sort(ql.begin(), ql.end());
	for(int i = 2; i <= n; i++) S[i].ini();
	for(auto &i : ql){
		for(; j < m && el[j].et > i.t; j++){
			Seg &cs = S[el[j].e], &ns = S[el[j].s];
			int nst = cs.get(el[j].et, sz);
			if(nst < inf){
				if(el[j].s == 1) av.push_back({nst, el[j].st});
				else ns.upd(el[j].st, nst);
			}
		}
		S[n].upd(i.t, i.t);
	}
	sort(av.begin(), av.end());
	for(auto &i : ql){
		auto t = upper_bound(av.begin(), av.end(), (Ans){i.t, 0});
		if(t == av.begin()) ans[i.i] = -1;
		else ans[i.i] = (--t)->v;
	}
	for(int i = 0; i < q; i++) printf("%d\n", ans[i]);
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:75: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:77:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &s, &e, &st, &et);
                                      ^
bus.cpp:81:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
bus.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
                  ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 3212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 3212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 193 ms 15584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 223 ms 15776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -