oj.uz

Submission #25583

# Submission time Handle Problem Language Result Execution time Memory
25583 2017-06-23T06:12:28 Z 김동현(#1072) 버스 (JOI14_bus) C++14
0 / 100
 766 ms 238628 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 Qry{
	int t, i;
	bool operator<(const Qry &oth) const {
		return t > oth.t;
	}
};

struct Nod{ int v, l, r; };

Nod nv[19000010];
int cnt;

const int sz = 86400002, inf = 1e9;
struct Seg{
	int rt;
	int mak(){ nv[cnt] = {inf, -1, -1}; return cnt++; }
	void ini(){ rt = mak(); }
	void upd(int x, int v, int c, int p, int q){
		if(p == q){ nv[c].v = min(nv[c].v, v); return; }
		int m = (p + q) / 2;
		if(x <= m){
			if(nv[c].l < 0) nv[c].l = mak();
			upd(x, v, nv[c].l, p, m);
			nv[c].v = min(nv[c].v, nv[nv[c].l].v);
		}
		else{
			if(nv[c].r < 0) nv[c].r = mak();
			upd(x, v, nv[c].r, m + 1, q);
			nv[c].v = min(nv[c].v, nv[nv[c].r].v);
		}
	}
	void upd(int x, int v){ upd(x + 1, v, rt, 1, sz); }
	int get(int s, int e, int c, int p, int q){
		if(e < p || q < s) return inf;
		if(s <= p && q <= e) return nv[c].v;
		int m = (p + q) / 2, ret = inf;
		if(nv[c].l >= 0) ret = min(ret, get(s, e, nv[c].l, p, m));
		if(nv[c].r >= 0) ret = min(ret, get(s, e, nv[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[300010];
vector<E> el;
vector<Qry> ql;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) S[i].ini();	
	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});
		S[n].upd(et, 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});
		S[n].upd(t, t);
	}
	ql.push_back({-1, q});
	sort(ql.begin(), ql.end());
	for(auto &i : ql){
		for(; j < m && el[j].et > i.t; j++){
			int nst = S[el[j].e].get(el[j].et, sz - 1);
			if(nst < inf){
				if(el[j].s == 1) S[1].upd(nst, -el[j].st);
				else S[el[j].s].upd(el[j].st, nst);
			}
		}
	}
	for(auto &i : ql){
		int t = -S[1].get(0, i.t);
		ans[i.i] = max(-1, t);
	}
	for(int i = 0; i < q; i++) printf("%d\n", ans[i]);
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:59: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:62: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:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
bus.cpp:69: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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 226256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 226256 KB Output is correct
2 Incorrect 106 ms 227892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 238628 KB Output is correct
2 Correct 583 ms 238628 KB Output is correct
3 Correct 513 ms 238628 KB Output is correct
4 Correct 549 ms 238628 KB Output is correct
5 Correct 589 ms 238628 KB Output is correct
6 Correct 506 ms 238628 KB Output is correct
7 Incorrect 563 ms 238628 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 238628 KB Output is correct
2 Correct 669 ms 238628 KB Output is correct
3 Correct 706 ms 238628 KB Output is correct
4 Correct 623 ms 238628 KB Output is correct
5 Correct 633 ms 238628 KB Output is correct
6 Correct 759 ms 238628 KB Output is correct
7 Incorrect 766 ms 238628 KB Output isn't correct
8 Halted 0 ms 0 KB -