| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 545663 |
2022-04-05T06:35:11 Z |
8e7 |
New Home (APIO18_new_home) |
C++17 |
|
1096 ms |
58476 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;
event(){x = val = l = r = 0;}
event(int a, int b, int c, int d){x = a, val = b, l = c, r = d;}
};
vector<event> lev, rev;
struct segtree{
int type; //1: max, 0:min
int seg[4*maxn];
void init(int cur, int l, int r) {
if (r <= l) return;
if (type == 0) seg[cur] = inf;
if (r - l == 1) return;
int m = (l + r) / 2;
init(cur*2, l, m), init(cur*2+1, m, r);
}
void modify(int cur, int l, int r, int ql, int qr, int v) {
if (r <= l || ql >= r || qr <= l || qr == ql) return;
if (ql <= l && qr >= r) {
if (type) seg[cur] = max(seg[cur], v);
else seg[cur] = min(seg[cur], v);
return;
}
int m = (l + r) / 2;
modify(cur*2, l, m, ql, qr, v);
modify(cur*2+1, m, r, ql, qr, v);
}
int query(int cur, int l, int r, int ind) {
if (r <= l || ind >= r || ind < l) return type ? -inf : inf;
int val = seg[cur];
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;
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(m, l, u, d));
rev.push_back(event(m, r, u, d));
};
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 != se.end() && 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;
ltr.init(1, 0, q);
for (int i = 0;i < q;i++) {
query cur = que[i];
while (rid < rev.size() && rev[rid].x <= cur.x) {
rtr.modify(1, 0, q, rev[rid].l, rev[rid].r, rev[rid].val);
rid++;
}
ans[cur.id] = rtr.query(1, 0, q, cur.ti) - cur.x;
}
for (int i = q - 1;i >= 0;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);
lid++;
}
ans[cur.id] = max(ans[cur.id], cur.x - ltr.query(1, 0, q, cur.ti));
}
for (int i = 0;i < q;i++) {
cout << (ans[i] >= inf/2 ? -1 : ans[i]) << "\n";
}
}
Compilation message
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:106:4: note: in expansion of macro 'debug'
106 | debug("seg", l, r, u, d);
| ^~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:151:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | while (rid < rev.size() && rev[rid].x <= cur.x) {
| ~~~~^~~~~~~~~~~~
new_home.cpp:159:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | while (lid < lev.size() && lev[lid].x >= cur.x) {
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 3 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10904 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
10904 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 3 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10904 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
10904 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
702 ms |
49960 KB |
Output is correct |
| 2 |
Incorrect |
612 ms |
47700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1096 ms |
58476 KB |
Output is correct |
| 2 |
Incorrect |
419 ms |
44476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 3 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10904 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
10904 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 3 |
Correct |
8 ms |
10836 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10904 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
10904 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
