oj.uz

답안 #676615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676615 2022-12-31T12:54:40 Z ymm 새 집 (APIO18_new_home) C++17
10 / 100
 2319 ms 93276 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

enum EventType {Rem, Add, Query};

struct Event {
	int time;
	EventType type;
	int store;
	int pos;
	int query_idx;
};

bool operator<(const Event &a, const Event &b) {
	return a.time < b.time || a.time == b.time && a.type < b.type;
}

vector<Event> evs;
vector<set<pii>> type_list;

struct Seg {
	int *t;
	int begin, end;
	
	void init(int b, int e) {
		t = new int[4 * (e-b)];
		fill(t, t + 4*(e-b), INT_MIN);
		begin = b;
		end = e;
	}
	void up_impl(int p, int x, int i, int b, int e) {
		if (e-b==1) {
			t[i] = x;
			return;
		}
		if (p < (b+e)/2)
			up_impl(p, x, 2*i+1, b, (b+e)/2);
		else
			up_impl(p, x, 2*i+2, (b+e)/2, e);
		t[i] = max(t[2*i+1], t[2*i+2]);
	}
	int get_impl(int l, int r, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i];
		if (r <= b || e <= l)
			return INT_MIN;
		return max(get_impl(l, r, 2*i+1, b, (b+e)/2),
		           get_impl(l, r, 2*i+2, (b+e)/2, e));
	}

	void up(int p, int x) { return up_impl(p, x, 0, begin, end); }
	int get(int l, int r) { return get_impl(l, r, 0, begin, end); }
} next_right;

int cnt_types, cnt_stores, cnt_queries;
vector<int> store_poses;

struct Store {
	int type;
	int pos;
	int b, e;
};
bool operator<(const Store &a, const Store &b) { return a.pos < b.pos; }
vector<Store> stores;

vector<int> ans;

void handle_add(Event ev)
{
	Store s = stores[ev.store];
	auto &list = type_list[s.type];
	auto it = list.upper_bound({s.pos, ev.store});
	int p = it == list.end()? INT_MAX: it->first;
	--it;
	next_right.up(it->second, s.pos);
	next_right.up(ev.store, p);
	list.insert({s.pos, ev.store});
}
void handle_rem(Event ev)
{
	Store s = stores[ev.store];
	auto &list = type_list[s.type];
	auto it = list.upper_bound({s.pos, ev.store});
	int p = it == list.end()? INT_MAX: it->first;
	--it; --it;
	next_right.up(it->second, p);
	next_right.up(ev.store, INT_MAX);
	list.erase({s.pos, ev.store});
}
void handle_query(Event ev)
{
	if (next_right.get(-cnt_types, 0) == INT_MAX) {
		ans[ev.query_idx] = -1;
		return;
	}
	int l = 0, r = store_poses.back();
	auto get = [&](int e) {
		e = lower_bound(store_poses.begin(), store_poses.end(), e) - store_poses.begin();
		return next_right.get(-cnt_stores, e);
	};
	while (l < r) {
		int m = (l + r)/2;
		int b = ev.pos - m, e = ev.pos + m + 1;
		if (get(b) < e)
			r = m;
		else
			l = m+1;
	}
	ans[ev.query_idx] = l;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> cnt_stores >> cnt_types >> cnt_queries;
	Loop (i,0,cnt_stores) {
		Store s;
		cin >> s.pos >> s.type >> s.b >> s.e;
		--s.pos; --s.b;
		stores.push_back(s);
		store_poses.push_back(s.pos);
	}
	sort(stores.begin(), stores.end());
	sort(store_poses.begin(), store_poses.end());
	Loop (i,0,cnt_stores) {
		evs.push_back({
			.time = stores[i].b,
			.type = Add,
			.store = i,
			.pos = stores[i].pos,
			.query_idx = -1,
		});
		evs.push_back({
			.time = stores[i].e,
			.type = Rem,
			.store = i,
			.pos = stores[i].pos,
			.query_idx = -1,
		});
	}
	Loop (i,0,cnt_queries) {
		int l, y;
		cin >> l >> y;
		--l; --y;
		evs.push_back({
			.time = y,
			.type = Query,
			.store = -1,
			.pos = l,
			.query_idx = i,
		});
	}
	sort(evs.begin(), evs.end());
	ans.resize(cnt_queries);
	type_list.resize(cnt_types+1);
	next_right.init(-cnt_types, cnt_stores);
	Loop (i,-cnt_types,0) {
		type_list[-i].insert({i, i});
		next_right.up(i, INT_MAX);
	}
	for (Event ev : evs) {
		switch (ev.type) {
		case Add:	handle_add(ev);		break;
		case Rem:	handle_rem(ev);		break;
		case Query:	handle_query(ev);	break;
		}
	}
	Loop (i,0,cnt_queries)
		cout << ans[i] << '\n';
}

Compilation message

new_home.cpp: In function 'bool operator<(const Event&, const Event&)':
new_home.cpp:20:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |  return a.time < b.time || a.time == b.time && a.type < b.type;
      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:134:13: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  134 |    .store = i,
      |             ^
new_home.cpp:141:13: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  141 |    .store = i,
      |             ^
new_home.cpp:155:17: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  155 |    .query_idx = i,
      |                 ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1634 ms 66664 KB Output is correct
2 Correct 2308 ms 57768 KB Output is correct
3 Correct 1271 ms 93240 KB Output is correct
4 Correct 1270 ms 71056 KB Output is correct
5 Correct 2116 ms 57276 KB Output is correct
6 Correct 2180 ms 57720 KB Output is correct
7 Correct 1245 ms 93276 KB Output is correct
8 Correct 1767 ms 71096 KB Output is correct
9 Correct 1855 ms 63384 KB Output is correct
10 Correct 2319 ms 58864 KB Output is correct
11 Correct 1892 ms 57252 KB Output is correct
12 Correct 1926 ms 58664 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1748 ms 59780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -