Submission #25586

#	Time	Username	Problem	Language	Result	Execution time	Memory
25586		kdh9949	버스 (JOI14_bus)	C++14	100 / 100	776 ms	237844 KiB

bus

#include <bits/stdc++.h>
using namespace std;

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

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 = max(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 = max(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 = max(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 = max(ret, get(s, e, nv[c].l, p, m));
		if(nv[c].r >= 0) ret = max(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, t[100010];
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[1].upd(st, st);
	}
	sort(el.begin(), el.end());
	scanf("%d", &q);
	for(int i = 0; i < q; i++){
		scanf("%d", t + i);
	}
	for(auto &i : el){
		int nst = S[i.s].get(0, i.st);
		if(nst >= 0) S[i.e].upd(i.et, nst);
	}
	for(int i = 0; i < q; i++){
		int v = S[n].get(0, t[i]);
		printf("%d\n", v < 0 ? -1 : v);
	}
}

Compilation message (stderr)

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:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", t + i);
                     ^

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50