| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 676615 |
2022-12-31T12:54:40 Z |
ymm |
New Home (APIO18_new_home) |
C++17 |
|
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,
| ^
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1748 ms |
59780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
