oj.uz

Submission #25570

# Submission time Handle Problem Language Result Execution time Memory
25570 2017-06-23T05:44:18 Z 김동현(#1072) 버스 (JOI14_bus) C++14
0 / 100
 376 ms 202696 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;
	}
};

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

Nod nv[16000010];
int cnt;

const int sz = 86400001, 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 = 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[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 = 1; i <= n; i++) S[i].ini();
	for(auto &i : ql){
		for(; j < m && el[j].et > i.t; j++){
			int nst = S[el[j].e].get(el[j].et, sz);
			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);
			}
		}
		S[n].upd(i.t, i.t);
	}
	sort(av.begin(), av.end());
	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:74: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:76: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:80:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
bus.cpp:82: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 Correct 0 ms 190324 KB Output is correct
2 Correct 0 ms 190324 KB Output is correct
3 Correct 0 ms 190324 KB Output is correct
4 Incorrect 0 ms 190324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 190324 KB Output is correct
2 Incorrect 56 ms 191960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 202696 KB Output is correct
2 Correct 246 ms 202696 KB Output is correct
3 Correct 259 ms 202696 KB Output is correct
4 Correct 266 ms 202696 KB Output is correct
5 Correct 263 ms 202696 KB Output is correct
6 Correct 193 ms 202696 KB Output is correct
7 Correct 196 ms 202696 KB Output is correct
8 Correct 199 ms 202696 KB Output is correct
9 Correct 219 ms 202696 KB Output is correct
10 Correct 293 ms 202696 KB Output is correct
11 Correct 199 ms 202696 KB Output is correct
12 Correct 353 ms 202696 KB Output is correct
13 Correct 376 ms 202696 KB Output is correct
14 Correct 316 ms 202696 KB Output is correct
15 Incorrect 233 ms 202696 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 202696 KB Output is correct
2 Correct 266 ms 202696 KB Output is correct
3 Correct 286 ms 202696 KB Output is correct
4 Correct 263 ms 202696 KB Output is correct
5 Correct 286 ms 202696 KB Output is correct
6 Correct 259 ms 202696 KB Output is correct
7 Incorrect 299 ms 202696 KB Output isn't correct
8 Halted 0 ms 0 KB -