| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 545632 |
2022-04-05T04:17:35 Z |
8e7 |
New Home (APIO18_new_home) |
C++17 |
|
5000 ms |
208760 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 2e8;
struct store{
int x, a, b;
store(){x = a = b = 0;}
store(int u, int v, int w){x = u, a = v, b = w;}
};
vector<store> seg[maxn];
struct query{
int x, ti, id;
query(){x = ti = id = 0;}
} que[maxn];
int ans[maxn];
struct event{
int x, val, l, r, ch;
event(){x = val = l = r = ch = 0;}
event(int a, int b, int c, int d, int e){x = a, val = b, l = c, r = d, ch = e;}
};
vector<event> lev, rev;
struct segtree{
int type; //1: max, 0:min
multiset<int> seg[4*maxn];
void modify(int cur, int l, int r, int ql, int qr, int v, int ch) {
if (r <= l || ql >= r || qr <= l) return;
if (ql <= l && qr >= r) {
if (ch == 1) seg[cur].insert(v);
else seg[cur].erase(seg[cur].find(v));
return;
}
int m = (l + r) / 2;
modify(cur*2, l, m, ql, qr, v, ch);
modify(cur*2+1, m, r, ql, qr, v, ch);
}
int query(int cur, int l, int r, int ind) {
if (r <= l) return type ? -inf : inf;
int val;
if (type) val = (seg[cur].size() ? *prev(seg[cur].end()) : -inf);
else val = (seg[cur].size() ? *seg[cur].begin() : inf);
if (r - l == 1) return val;
int m = (l + r) / 2, rec;
if (ind < m) rec = query(cur*2, l, m, ind);
else rec = query(cur*2+1, m, r, ind);
return type ? max(val, rec) : min(val, rec);
}
} ltr, rtr;
int main() {
io
int n, k, q;
cin >> n >> k >> q;
vector<int> tv;
for (int i = 1;i <= k;i++) seg[i].push_back(store(-inf, 0, inf));
for (int i = 0;i < n;i++) {
store s;
int ty;
cin >> s.x >> ty >> s.a >> s.b;
s.b++;
//tv.push_back(s.a), tv.push_back(s.b);
seg[ty].push_back(s);
}
for (int i = 1;i <= k;i++) seg[i].push_back(store(inf, 0, inf));
for (int i = 0;i < q;i++) {
cin >> que[i].x >> que[i].ti;
que[i].id = i;
tv.push_back(que[i].ti);
}
sort(tv.begin(), tv.end());
tv.resize(int(unique(tv.begin(), tv.end()) - tv.begin()));
//pary(tv.begin(), tv.end());
auto conv = [&] (int x){
return lower_bound(tv.begin(), tv.end(), x) - tv.begin();
};
for (int i = 1;i <= k;i++) {
set<pii> se;
debug("type", i);
auto add_seg = [&] (int l, int r, int u, int d) {
if (d <= u) return;
int m = (l + r + 1) / 2;
debug("seg", l, r, u, d);
lev.push_back(event(l, l, u, d, 1));
lev.push_back(event(m, l, u, d, -1));
rev.push_back(event(m, r, u, d, 1));
rev.push_back(event(r, r, u, d, -1));
};
sort(seg[i].begin(), seg[i].end(), [&] (store x, store y){return x.x < y.x;});
for (auto &p:seg[i]) {
p.a = conv(p.a), p.b = conv(p.b);
if (se.empty()) {
se.insert({p.a, p.x});
se.insert({p.b+1, p.x});
} else {
if (p.a == p.b) continue;
auto it = se.lower_bound(make_pair(p.a, -inf));
int cur = p.a;
while (it != se.end() && it->ff <= p.b) {
if (it != se.begin()) add_seg(prev(it)->ss, p.x, cur, it->ff);
cur = it->ff;
it = next(it);
}
if (it != se.begin()) add_seg(prev(it)->ss, p.x, cur, p.b);
it = se.lower_bound(make_pair(p.a, -inf));
int last = prev(it)->ss;
while (it->ff < p.b) {
last = it->ss;
se.erase(it);
it = se.lower_bound(make_pair(p.a, -inf));
}
se.insert(make_pair(p.a, p.x));
if (it->ff > p.b) {
se.insert(make_pair(p.b, last));
}
}
}
}
for (int i = 0;i < q;i++) que[i].ti = conv(que[i].ti);
sort(que, que + q, [&] (query x, query y){return x.x < y.x;});
sort(lev.begin(), lev.end(), [&] (event x, event y){return x.x < y.x;});
sort(rev.begin(), rev.end(), [&] (event x, event y){return x.x < y.x;});
int lid = 0, rid = 0;
rtr.type = 1;
for (int i = 0;i < q;i++) {
query cur = que[i];
while (lid < lev.size() && lev[lid].x <= cur.x) {
ltr.modify(1, 0, q, lev[lid].l, lev[lid].r, lev[lid].val, lev[lid].ch);
lid++;
}
while (rid < rev.size() && rev[rid].x <= cur.x) {
rtr.modify(1, 0, q, rev[rid].l, rev[rid].r, rev[rid].val, rev[rid].ch);
rid++;
}
ans[cur.id] = max(cur.x - ltr.query(1, 0, q, cur.ti), rtr.query(1, 0, q, cur.ti) - cur.x);
}
for (int i = 0;i < q;i++) {
cout << (ans[i] >= inf/2 ? -1 : ans[i]) << "\n";
}
}
/*
*/
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
new_home.cpp:98:3: note: in expansion of macro 'debug'
98 | debug("type", i);
| ^~~~~
new_home.cpp: In lambda function:
new_home.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
new_home.cpp:102:4: note: in expansion of macro 'debug'
102 | debug("seg", l, r, u, d);
| ^~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:148:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | while (lid < lev.size() && lev[lid].x <= cur.x) {
| ~~~~^~~~~~~~~~~~
new_home.cpp:152:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | while (rid < rev.size() && rev[rid].x <= cur.x) {
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
123568 KB |
Output is correct |
| 2 |
Correct |
54 ms |
123584 KB |
Output is correct |
| 3 |
Correct |
57 ms |
123528 KB |
Output is correct |
| 4 |
Correct |
61 ms |
123580 KB |
Output is correct |
| 5 |
Execution timed out |
5094 ms |
123724 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
123568 KB |
Output is correct |
| 2 |
Correct |
54 ms |
123584 KB |
Output is correct |
| 3 |
Correct |
57 ms |
123528 KB |
Output is correct |
| 4 |
Correct |
61 ms |
123580 KB |
Output is correct |
| 5 |
Execution timed out |
5094 ms |
123724 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5099 ms |
193088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5109 ms |
208760 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
123568 KB |
Output is correct |
| 2 |
Correct |
54 ms |
123584 KB |
Output is correct |
| 3 |
Correct |
57 ms |
123528 KB |
Output is correct |
| 4 |
Correct |
61 ms |
123580 KB |
Output is correct |
| 5 |
Execution timed out |
5094 ms |
123724 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
123568 KB |
Output is correct |
| 2 |
Correct |
54 ms |
123584 KB |
Output is correct |
| 3 |
Correct |
57 ms |
123528 KB |
Output is correct |
| 4 |
Correct |
61 ms |
123580 KB |
Output is correct |
| 5 |
Execution timed out |
5094 ms |
123724 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
